PTA A_1072 Gas Station

798236606

传送门：https://pintia.cn/problem-sets/9 ... /994805396953219072

解：
迪杰斯特拉

1. #include <cstdio>
   
2. #include <climits>
   
3. #include <cstring>
   
4. #include <algorithm>
   
5. 
   
6. using namespace std;
   
7. 
   
8. const int maxn = 1050;
   
9. 
   
10. int n, m, k, ds;
    
11. int d[maxn];
    
12. bool vis[maxn];
    
13. int G[maxn][maxn];
    
14. 
    
15. int trans(char *s)
    
16. {
    
17.     int id;
    
18. 
    
19.     if (*s == 'G')
    
20.     {
    
21.         sscanf(s + 1, "%d", &id);
    
22.         id += n;
    
23.     }
    
24.     else
    
25.         sscanf(s, "%d", &id);
    
26. 
    
27.     return id;
    
28. }
    
29. 
    
30. void DJS(int st)
    
31. {
    
32.     fill(d, d + maxn, INT_MAX);
    
33.     memset(vis, false, sizeof(vis));
    
34. 
    
35.     d[st] = 0;
    
36. 
    
37.     for (int i = 1; i < n + m; i++)
    
38.     {
    
39.         int u  = -1, min = INT_MAX;
    
40. 
    
41.         for (int j = 1; j <= n + m; j++)
    
42.             if (!vis[j] && d[j] < min) min = d[u = j];
    
43. 
    
44.         if (u == -1) return;
    
45. 
    
46.         vis[u] = true;
    
47. 
    
48.         for (int v = 1; v <= n + m; v++)
    
49.         {
    
50.             if (vis[v] || G[u][v] == INT_MAX) continue;
    
51.             if (G[u][v] + d[u] < d[v]) d[v] = G[u][v] + d[u];
    
52.         }
    
53.     }
    
54. }
    
55. 
    
56. int main(void)
    
57. {
    
58.     // freopen("input.txt", "r", stdin);
    
59.     scanf("%d %d %d %d", &n, &m, &k, &ds);
    
60.         
    
61.     fill(G[0], G[0] + maxn * maxn, INT_MAX);
    
62.    
    
63.     while (k--)
    
64.     {
    
65.         char s1[5], s2[5];
    
66.         int a, b, l;
    
67. 
    
68.         scanf("%s %s %d", s1, s2, &l);
    
69.         a = trans(s1);
    
70.         b = trans(s2);
    
71. 
    
72.         G[a][b] = G[b][a] = l;
    
73.     }
    
74. 
    
75.     int max_id = -1, max = INT_MIN;
    
76.     double ave[maxn];
    
77. 
    
78.     for (int i = n + 1; i <= n + m; i++)
    
79.     {
    
80.         DJS(i);
    
81. 
    
82.         int temp = d[1], total = 0;
    
83.         bool flag = false;
    
84.         for (int j = 1; j <= n; j++)
    
85.         {
    
86.             if (d[j] > ds)
    
87.             {
    
88.                 flag = true;
    
89.                 break;
    
90.             }
    
91. 
    
92.             total += d[j];
    
93.             if (d[j] < temp) temp = d[j];
    
94.         }
    
95. 
    
96.         if (flag) continue;
    
97. 
    
98.         ave[i] = (double)total / (double)n;   
    
99. 
    
100.         if (temp > max || (temp == max && ave[i] < ave[max_id]))
     
101.         {
     
102.             max = temp;
     
103.             max_id = i;
     
104.         }
     
105.     }
     
106. 
     
107.     if (max_id == -1) puts("No Solution");
     
108.     else printf("G%d\n%.1f %.1f\n", max_id - n, (double)max, ave[max_id]);
     
109.    
     
110.     return 0;
     
111. }

复制代码