【HDOJ】1706 The diameter of graph

  1 /* 1706 */
  2 #include <iostream>
  3 #include <string>
  4 #include <map>
  5 #include <queue>
  6 #include <set>
  7 #include <stack>
  8 #include <vector>
  9 #include <deque>
 10 #include <algorithm>
 11 #include <cstdio>
 12 #include <cmath>
 13 #include <ctime>
 14 #include <cstring>
 15 #include <climits>
 16 #include <cctype>
 17 #include <cassert>
 18 #include <functional>
 19 #include <iterator>
 20 #include <iomanip>
 21 using namespace std;
 22 //#pragma comment(linker,"/STACK:102400000,1024000")
 23 
 24 #define sti                set<int>
 25 #define stpii            set<pair<int, int> >
 26 #define mpii            map<int,int>
 27 #define vi                vector<int>
 28 #define pii                pair<int,int>
 29 #define vpii            vector<pair<int,int> >
 30 #define rep(i, a, n)     for (int i=a;i<n;++i)
 31 #define per(i, a, n)     for (int i=n-1;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_JUDGE
113         printf("time = %d.\n", (int)clock());
114     #endif
115     
116     return 0;
117 }