题意：找出一个0，1，矩阵
分析：
转换思维的题啊，由一道让人不知如何下手的题，转换为了最短路基本思路就是把矩阵看做一个图，图中有n个点，1号点出度为1，
n号点入度为1，其它点出度和入度相等，路径长度都是非负数，等价于一条从1号节点到n号节点的路径，故Xij=1表示需要经
过边(i,j)，代价为Cij。Xij=0表示不经过边(i,j)。注意到Cij非负且题目要求总代价最小，因此最优答案的路径一定可以对应一条简单路径。
最终，我们直接读入边权的邻接矩阵，跑一次1到n的最短路即可，记最短路为path。
漏了如下的情况B：
从1出发，走一个环（至少经过1个点，即不能是自环），回到1；从n出发，走一个环（同理），回到n。
也就是1和n点的出度和入度都为1，其它点的出度和入度为0.
由于边权非负，于是两个环对应着两个简单环。
因此我们可以从1出发，找一个最小花费环，记代价为c1,
再从n出发，找一个最小花费环，记代价为c2。
（只需在最短路算法更新权值时多加一条记录即可：if(i==S) cir=min(cir,dis[u]+g[u][i])）
故最终答案为min(path,c1+c2)
#include<stdio.h> #include<string.h> #define clr(x)memset(x,0,sizeof(x)) #define INF 0x1f1f1f1f #define maxn 333 #define min(a,b)(a)<(b)?(a):(b) int g[maxn][maxn]; int d[maxn]; int q[1000]; int v[maxn]; int n; void spfa(int st,int en) { int i,u,front,rear; front=rear=0; clr(v); d[st]=INF; for(i=1;i<=n;i++) { if(i!=st) { v[i]=1; d[i]=g[st][i]; q[rear++]=i; } } while(front!=rear) { u=q[front++]; v[u]=0; for(i=1;i<=n;i++) { if(d[u]+g[u][i]<d[i]) { d[i]=d[u]+g[u][i]; if(!v[i]) { v[i]=1; q[rear++]=i; } } } } } int main() { int res,i,j,ds,dn,di; while(scanf("%d",&n)!=EOF) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&g[i][j]); spfa(1,n); di=d[n]; ds=d[1]; spfa(n,n); dn=d[n]; res=min(ds+dn,di); printf("%d\n",res); } return 0; }