kuangbin_ShortPath R (HDU 4370)

#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#define INF 0x3F3F3F3F
using namespace std;

int n, val[310][310];
int dist[310];
bool vis[310];

void spfa(int s)
{
    //计算最短闭环 因此入队节点不是1而是其他所有点
    memset(vis, false, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(i == s) continue;
        dist[i] = val[s][i];
        q.push(i);
        vis[i] = true;
    }
    while(!q.empty()){
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = 1; i <= n; i++){
            if(i == u) continue; 
            if(dist[i] > dist[u] + val[u][i]){
                dist[i] = dist[u] + val[u][i];
                if(!vis[i]){
                    vis[i] = true;
                    q.push(i);
                }
            }
        }
    }
}

int main()
{
    int path, dist1, distn;
    int ans;
    while(~scanf("%d", &n)){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                scanf("%d", &val[i][j]);
            }
        }
        spfa(1);
        path = dist[n];
        dist1 = dist[1];
        spfa(n);
        distn = dist[n];
        printf("%d\n", min(dist1 + distn, path));
    }
    return 0;
}