hdu6026 Deleting Edges（Dijkstra+思路）

我一直想不明白的是，它的乘法是如何保证n-1条边的。后来画了一张图大概能明白了。

结合最后的乘法二层循环的代码来看，当i=4的时候，j有1和3满足条件，3满足不用说是迪杰斯特拉本身跑出来的，1满足条件，而中间的点2、3也可以有自己本身的路径达到，最后满足共n-1条边。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<set>
 8 #define IO ios::sync_with_stdio(false);cin.tie(0);
 9 #define INF 0x3f3f3f3f
10 typedef long long ll;
11 using namespace std;
12 const int MOD=1e9+7;
13 ll n, dist[110], vis[110], a[110][110];
14 char b[110][110];
15 void dijkstra()
16 {
17     for(int i = 0; i < n; i++){
18         dist[i] = INF;
19     }
20     dist[0]=0;
21     for(int i = 0; i < n; i++){
22         ll mini = INF, k=-1;
23         for(int j = 0; j < n; j++){
24             if(!vis[j]&&dist[j]<mini){
25                 mini = dist[j];
26                 k = j;
27             }
28         }
29         vis[k] = 1;
30         for(int j = 0; j < n; j++){
31             if(!vis[j]&&a[k][j]&&dist[j] > dist[k]+a[k][j]){//0是不通 
32                 dist[j] = dist[k]+a[k][j];
33             } 
34         }
35     }
36 }
37 int main()
38 {
39     while(cin >> n){
40         memset(vis, 0, sizeof(vis));
41         for(int i = 0; i < n; i++){
42             cin >> b[i];
43             for(int j = 0; j < n; j++){
44                 a[i][j] = b[i][j]-'0';
45             } 
46         } 
47         dijkstra();
48         /*for(int i = 0; i < n; i++){
49             cout << dist[i] << " ";
50         } cout << endl;*/
51         ll tmp, ans=1;
52         for(int i = 1; i < n; i++){
53             tmp = 0;
54             for(int j = 0; j < n; j++){
55                 if(a[j][i]&&dist[i] == dist[j]+a[j][i]){//0是不通 
56                     tmp++;
57                 }
58             }
59             ans = (ans*tmp)%MOD;
60         }
61         cout << ans << endl;
62     } 
63     return 0;
64 }