hdu4370（spfa最短路最小环）

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4370

很久之前做的题了，今天做一道spfa的题忽然想起这道。。。

题目给出的是矩阵，对应图的出度、入度等。。

想到了求1到n的最短路，没想到求最小环的情况。。

有人说不好想，其实是理解不到位。。

想想自己很多时间也觉得有些题根本想不出来啊，大概也是对很多知识理解不深刻。。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<queue>
 5 using namespace std;
 6 const int maxn=350;
 7 const int inf=0x3f3f3f3f;
 8 int n;
 9 int pic[maxn][maxn];
10 int dis[maxn];
11 int inq[maxn];
12 void spfa(int s)
13 {
14 
15     queue<int> q;
16     while(!q.empty()) q.pop();
17     for(int i=1;i<=n;i++)              
18     {
19         inq[i]=0;
20         if(i==s) dis[i]=inf; //求最小环
21         else {
22             dis[i]=pic[s][i];  //
23             inq[i]=1;
24             q.push(i);
25         }
26     }
27     while(!q.empty())
28     {
29         int u=q.front();
30         q.pop();
31         inq[u]=0;
32         for(int i=1;i<=n;i++)
33         {
34             if(dis[i]>dis[u]+pic[u][i])
35             {
36                 dis[i]=dis[u]+pic[u][i];
37 
38                 if(!inq[i])
39                 {
40                     inq[i]=1;
41                     q.push(i);
42                 }
43             }
44         }
45     }
46 
47 }
48 
49 int main()
50 {
51     while(scanf("%d",&n)!=EOF&&n)
52     {
53         for(int i=1;i<=n;i++)
54             for(int j=1;j<=n;j++)
55                 scanf("%d",&pic[i][j]);
56         spfa(1);
57         int s1=dis[1];  //1的最小环
58         int ans=dis[n];//1到n的最短路
59         spfa(n);
60         int s2=dis[n];// n的最小环
61         ans=min(ans,s1+s2);
62         printf("%d
",ans);
63     }
64 }