L2-001 紧急救援（25 分)

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数

第二行给出

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从

输入样例:

4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2

输出样例:

2 60
0 1 3

作者: 陈越

单位: 浙江大学

时间限制: 200 ms

内存限制: 64 MB

PTA特色题目麻烦

经典题目模板求最短路的数目求救援队最大的数目

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <vector>
 4 #include <queue>
 5 #include <algorithm>
 6 #include <stack>
 7 using namespace std;
 8 int N, M, S, D;
 9 const int inf = 2e9;
10 const int si = 505;
11 bool vis[si];
12 struct ed{
13     int to, t;
14     ed(int a, int b) {
15         to = a; t = b;
16     }
17 };
18 struct node{
19     int id, time;
20     node(int a, int b) {
21         id = a; time = b;
22     }
23     bool operator < (const node x) const {
24         return time > x.time;
25     }
26 };
27 vector<ed> G[si];
28 int jiuyuan[si], dis[si], pre[si];
29 int roadcnt[si], getjy[si];
30 
31 priority_queue<node> q;
32 void dijkstra() {
33     fill(dis, dis + N , inf);
34     fill(vis, vis + N , 0);
35     dis[S] = 0;
36     roadcnt[S] = 1;
37     getjy[S] = jiuyuan[S];
38     q.push(node(S, 0));
39 
40     while (!q.empty()) {
41         node no = q.top(); q.pop();
42         int id = no.id, time = no.time, jy = getjy[id];
43         if (vis[id]) continue;
44         vis[id] = 1;
45         for (int i = 0; i < G[id].size(); i++) {
46             int to = G[id][i].to, t = G[id][i].t;
47             int nt = t + time;
48             int njy = jy + jiuyuan[to];
49             if (dis[to] == nt) {
50                 roadcnt[to] += roadcnt[id];
51                 if (njy > getjy[to]) {
52                     getjy[to] = njy;
53                     pre[to] = id;
54                 }
55             }
56             else if (dis[to] > nt) {
57                 dis[to] = nt;
58                 getjy[to] = njy;
59                 roadcnt[to] = roadcnt[id];
60                 pre[to] = id;
61                 q.push(node(to, nt));
62             }
63         }
64     }
65 }
66 int main() {
67     cin >> N >> M >> S >> D;
68     for (int i = 0; i < N; i++)
69         cin >> jiuyuan[i];
70     for (int i = 0; i < M; i++) {
71         int a, b, c;
72         cin >> a >> b >> c;
73         G[a].push_back(ed(b, c));
74         G[b].push_back(ed(a, c));
75     }
76     dijkstra();
77     printf("%d %d
", roadcnt[D], getjy[D]);
78     int crt = D;
79     stack<int> stk;
80     while (1) {
81         stk.push(crt);
82         if (crt == S) break;
83         crt = pre[crt];
84     }
85     while (1) {
86         cout << stk.top();
87         stk.pop();
88         if (stk.empty()) {
89             cout << endl;
90             break;
91         }
92         else cout << " ";
93     }
94     return 0;
95 }

L2-001 紧急救援 （25 分)

输入格式:

输出格式:

输入样例:

输出样例:

L2-001 紧急救援（25 分)