本文共 2390 字，大约阅读时间需要 7 分钟。
这么个简单的题目居然没有人题解。floyd中计算数目，同时注意重边。
1 /* 1706 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int INF = 0x3f3f3f3f; 43 const int maxn = 105; 44 int dis[maxn][maxn]; 45 int M[maxn][maxn]; 46 int cnt[maxn][maxn]; 47 int n, m; 48 49 void floyd() { 50 rep(k, 1, n+1) { 51 rep(i, 1, n+1) { 52 if (M[i][k]>=INF || i==k) 53 continue; 54 rep(j, 1, n+1) { 55 if (M[k][j]>=INF || k==j || i==j) 56 continue; 57 if (M[i][j] > M[i][k]+M[k][j]) { 58 M[i][j] = M[i][k] + M[k][j]; 59 cnt[i][j] = cnt[i][k] * cnt[k][j]; 60 } else if (M[i][j] == M[i][k]+M[k][j]) { 61 cnt[i][j] += cnt[i][k] * cnt[k][j]; 62 } 63 } 64 } 65 } 66 } 67 68 int main() { 69 ios::sync_with_stdio(false); 70 #ifndef ONLINE_JUDGE 71 freopen("data.in", "r", stdin); 72 freopen("data.out", "w", stdout); 73 #endif 74 75 int u, v, w; 76 int mx; 77 int ans; 78 79 while (scanf("%d %d", &n, &m)!=EOF) { 80 memset(M, 0x3f, sizeof(M)); 81 memset(cnt, 0, sizeof(cnt)); 82 rep(i, 0, m) { 83 scanf("%d %d %d", &u, &v, &w); 84 if (u == v) 85 continue; 86 if (M[u][v] > w) { 87 M[u][v] = M[v][u] = w; 88 cnt[u][v] = cnt[v][u] = 1; 89 } else if (M[u][v] == w) { 90 ++cnt[u][v]; 91 ++cnt[v][u]; 92 } 93 } 94 floyd(); 95 ans = 0; 96 mx = -1; 97 rep(i, 1, n+1) { 98 rep(j, 1, i) { 99 if (M[i][j]==INF || i==j)100 continue;101 if (mx < M[i][j]) {102 mx = M[i][j];103 ans = cnt[i][j];104 } else if (mx == M[i][j]) {105 ans += cnt[i][j];106 }107 }108 }109 printf("%d %d\n", mx, ans);110 }111 112 #ifndef ONLINE_JUDGE113 printf("time = %d.\n", (int)clock());114 #endif115 116 return 0;117 }
转载于:https://www.cnblogs.com/bombe1013/p/4985070.html