L2-001 紧急救援 （25 分)
作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，一路上召集尽可能多的救援队。
输入格式:
输入第一行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0 ~ (N−1)；M是快速道路的条数；S是出发地的城市编号；D是目的地的城市编号。
第二行给出N个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。
输出格式:
第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。
输入样例:
代码语言：javascript复制4 5 0 3
20 30 40 10
0 1 1
1 3 2
0 3 3
0 2 2
2 3 2输出样例:
代码语言：javascript复制2 60
0 1 3代码语言：javascript复制&：虽然和一开始的思路有点差别，不过也是没啥大问题的 &：先用 dijkstra 跑一遍，这个时候可以得到从 s 点到 d 点的最短路径。然后跑 dfs ，判断从 s 点出发，是否会出现和 s 到 d 这点一样长度的路线，如果有的话，需要把这条路线的救援队数量记录一下，与后面发生的相同的比较，记录最大值和路径。 &：也是第一次使用 vector 直接赋值，以前都是跑个for,Orz.
#include <bits/stdc .h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 550;
int n,m,s,d,Maxv,cnt;
int val[maxn],vis[maxn],dist[maxn];
int G[maxn][maxn];
vector<int>ans,pre;
void dijkstra()
{
memset(vis,0,sizeof(vis));
for(int i = 0; i < n; i )dist[i] = G[s][i];
int Min = inf;
int v = -1;
for(int i = 0; i < n; i )
{
Min = inf;
v = -1;
for(int j = 0; j < n; j )
{
if(!vis[j] && dist[j] < Min)
{
Min = dist[j];
v = j;
}
}
vis[v] = 1;
for(int j = 0; j < n; j )
{
if(!vis[j] && dist[j] > dist[v] G[v][j])
{
dist[j] = dist[v] G[v][j];
}
}
}
}
void dfs(int x, int w)
{
if(x == d)
{
if(w > Maxv)
{
Maxv = w;
ans = pre;
}
cnt ;
return ;
}
for(int i = 0; i < n; i )
{
if(G[x][i] && !vis[i] && dist[i] == dist[x] G[x][i])
{
vis[i] = 1;
pre.push_back(i);
dfs(i,w val[i]);
pre.pop_back();
vis[i] = 0;
}
}
}
int main()
{
int u,v,w;
scanf("%d %d %d %d", &n, &m, &s, &d);
for(int i = 0; i < n; i )
{
scanf("%d", &val[i]);
}
for(int i = 0; i <= n; i )
{
for(int j = 0; j <= n; j )
{
if(i != j)G[i][j] = inf;
else G[i][j] = 0;
}
}
for(int i = 0; i < m; i )
{
scanf("%d %d %d", &u, &v, &w);
G[u][v] = w;
G[v][u] = w;
}
dijkstra();
Maxv = 0;
cnt = 0;
memset(vis,0,sizeof(vis));
pre.push_back(s);
dfs(s,val[s]);
printf("%d %dn",cnt,Maxv);
int len = ans.size();
for(int i = 0; i < len; i )
{
if(i == 0) printf("%d",ans[i]);
else printf(" %d",ans[i]);
}
printf("n");
return 0;
}
