天梯 L2 紧急救援（dijkstra变形+记录路径）

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


题目大意：
　　求从S到D的最短路数量、这些最短路中能够召集的最多的救援队数量，并输出路径。

解题思路：
　　dijkstra跑最短路，在求最短路的过程中更新最短路的数量、救援队的数量、该城市的前一个城市。

#include<bits/stdc++.h>
#define ll long long
#define exp 1e-8
using namespace std;
const int N = 500+5;
const int INF = 0x3f3f3f3f;
int a[N][N],pre[N],w[N],c[N],low[N],num[N],vis[N];
int n,m,s,d,u,v,x;
void dij(){
    for (int i=0;i<n;i++){
        low[i]=a[s][i];
        num[i]=c[i]=vis[i]=0;
        pre[i]=i;
    }
    num[s]=1;
    pre[s]=s;
    c[s]=w[s];
    for (int i=0;i<n;i++){
        int k=-1,mi=INF;
        for (int j=0;j<n;j++){
            if (!vis[j]&&low[j]<mi){
                k=j;
                mi=low[j];
            }
        }
        vis[k]=1;
        for (int j=0;j<n;j++){
            if (!vis[j]&&a[k][j]+low[k]<low[j]){
                low[j]=a[k][j]+low[k];
                pre[j]=k;
                c[j]=c[k]+w[j];
                num[j]=num[k];
            }else if (!vis[j]&&a[k][j]+low[k]==low[j]){
                if (c[j]<c[k]+w[j]){
                    c[j]=c[k]+w[j];
                    pre[j]=k;
                }
                num[j]+=num[k];
            }
        }
    }
}
void print(int z){
    if (pre[z]==s) {
        printf(" %d",z);
        return ;
    }
    print(pre[z]);
    printf(" %d",z);
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&d);
    memset(a,INF,sizeof(a));
    for (int i=0;i<n;i++) scanf("%d",&w[i]),a[i][i]=0;
    for (int i=0;i<m;i++){
        scanf("%d%d%d",&u,&v,&x);
        a[u][v]=a[v][u]=min(a[u][v],x);
    }
    dij();
    printf("%d %d
",num[d],c[d]);
    printf("%d",s);
    print(d);
    return 0;
}

View Code

天梯 L2 紧急救援 （dijkstra变形+记录路径）

输入格式:

输出格式:

输入样例:

输出样例:

天梯 L2 紧急救援（dijkstra变形+记录路径）