1003 Emergency 25

 

 

1. #include <cstdio>
2. #include <vector>
3. #include <algorithm>
5. using namespace std;
6. const int maxn = 505;
7. int G[maxn][maxn],rescueNum[maxn],vis[maxn]={0},dis[maxn],teamNum[maxn]={0},pathNum[maxn]={0};
8. int n,m,s,e,INF=1000000000;
10. int findNotVisMin(){
11.     int minIdx = -1;
12.     int minDis = INF;
13.     for(int i = 0; i < n; i++){
14.         if(vis[i] == 0 && dis[i] < minDis){
15.             minIdx = i;
16.             minDis = dis[i];
17.         }
18.     }
19.     return minIdx;
20. }
21. int main() {
22.     scanf("%d%d%d%d", &n, &m, &s, &e);
23.     int tmp,from,to,weight;
24.     for(int i = 0; i < n; i++){
25.         scanf("%d", &tmp);
26.         rescueNum[i] = tmp;
27.     }
28.     fill(G[0], G[0]+maxn*maxn, INF);
29.     for(int i = 0; i < m; i++){
30.         scanf("%d%d%d", &from, &to, &weight);
31.         G[from][to] = G[to][from] = weight;
32.     }
33.     fill(dis, dis+maxn, INF);
34.     dis[s] = 0;
35.     teamNum[s] = rescueNum[s];
36.     pathNum[s] = 1;
37.     for(int i = 0; i < n; i++){
38.         int min = findNotVisMin();
39.         if(min == -1) break;
40.         vis[min] = 1;
41.         for(int j = 0; j < n; j++){
42.             if(vis[j] == 0 && G[min][j] != INF){
43.                 if(dis[min]+G[min][j] < dis[j]){
44.                     dis[j] = dis[min]+G[min][j];
45.                     pathNum[j] = pathNum[min];
46.                     teamNum[j] = teamNum[min] + rescueNum[j];
47.                 }else if(dis[min]+G[min][j] == dis[j]){
48.                     pathNum[j] += pathNum[min];
49.                     if(teamNum[min]+rescueNum[j] > teamNum[j]){
50.                         teamNum[j] = teamNum[min]+rescueNum[j];
51.                     }
52.                 }
53.             }
54.         }
55.     }
56.     printf("%d %d\n", pathNum[e], teamNum[e]);
57.     return 0;
58. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。