HDU4370(0 or 1)

链接：https://vjudge.net/contest/254476#problem/R
思路：这道题很巧妙，我以为是模拟建图，没有看出来新矩阵可以看作一个1-n的邻接矩阵，且保证1的出度为1，n的入度为1，相当于求一个1-n的最短路，或者是一个1出发的自环+一个n出发的自环，只要看出来了这个题就很简单了，按思路建图跑两遍最短路即可。（注意1开始的距离并不是0，所以迪杰斯特拉不适用，这时候用spfa比较好）
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 500*500;
const int INF  = 1e9;

int a[500][500];
typedef pair<int,int> P;

struct edge{
    int from,to,dist;
};

struct Dij{
    int n,m;
    vector<int> G[maxn];
    vector<edge> edges;
    int d[maxn];
    int inq[maxn];
    int cnt[maxn];

    void init(int n){
        this->n = n;
        for(int i=0;i<=n;i++)G[i].clear();
        edges.clear();
    }

    void addedge(int from,int to,int dist){
        edges.push_back(edge{from,to,dist});
        m = edges.size();
        G[from].push_back(m-1);
    }

        bool spfa(int s){
        queue<int> Q;
        memset(inq,0,sizeof(inq));
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;i++)
    {
        if(i==s) 
        {
            d[s]=1e9;continue;
        }
        d[i]=a[s][i];
        inq[i]=1;
        Q.push(i);
    }
        Q.push(s);
        while(!Q.empty()){
            int u = Q.front();
            Q.pop();
            inq[u] = false;
            for(int i=0;i<G[u].size();i++){
                edge& e = edges[G[u][i]];
                if(d[e.to]>d[u]+e.dist){
                    d[e.to] = d[u] + e.dist;
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to] = true;
                        if(++cnt[e.to]>n){                      
                            return true;
                        }
                    }
                }
            }
        }
            return false;
    }
}solver;

int n;

int main(){
    while(~scanf("%d",&n)){
    solver.init(n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            solver.addedge(i,j,a[i][j]);
        }
    }
    solver.spfa(1);
    int ans1 = solver.d[n];
    int loop1 = solver.d[1];
    solver.spfa(n);
    int loop2 = solver.d[n];
    printf("%d\n",min(loop1 + loop2,ans1));
    }
    return 0;
}