hdu 1596 find the safest road （变形SP && dij+heap）

　　变形最短路问题，给出邻接矩阵，要求求出给定点对间安全率最大值。

　　这题可以用dijkstra+heap来做。对于每一个查询，做一次dij即可。

代码如下：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <queue>
 6 
 7 using namespace std;
 8 
 9 const int N = 1111;
10 double wt[N][N];
11 bool vis[N];
12 #define _clr(x) memset(x, 0, sizeof(x))
13 typedef pair<double, int> PDBI;
14 priority_queue<PDBI> priq;
15 
16 double dij(int s, int t, int n) {
17     while (!priq.empty()) priq.pop();
18     _clr(vis);
19     for (int i = 0; i < n; i++) priq.push(PDBI(wt[s][i], i));
20     while (!priq.empty()) {
21         double w = priq.top().first;
22         int id = priq.top().second;
23         priq.pop();
24         if (vis[id]) continue;
25 //        cout << "id!!! " << id << endl;
26         vis[id] = true;
27         if (id == t) return w;
28         for (int i = 0; i < n; i++) {
29             if (vis[i]) continue;
30             if (wt[s][i] < wt[s][id] * wt[id][i]) {
31                 wt[s][i] = wt[s][id] * wt[id][i];
32                 priq.push(PDBI(wt[s][i], i));
33             }
34         }
35     }
36     return wt[s][t];
37 }
38 
39 int main() {
40 //    freopen("in", "r", stdin);
41     int n, m;
42     while (~scanf("%d", &n)) {
43         for (int i = 0; i < n; i++) {
44             for (int j = 0; j < n; j++) {
45                 scanf("%lf", &wt[i][j]);
46             }
47         }
48         scanf("%d", &m);
49         for (int i = 0, x, y; i < m; i++) {
50             scanf("%d%d", &x, &y);
51             double ans = dij(x - 1, y - 1, n);
52             if (ans < 1e-100) puts("What a pity!");
53             else printf("%.3f
", ans);
54         }
55     }
56     return 0;
57 }

View Code

——written by Lyon