L2-001. 緊急救援 - Dijkastra+變形 ||優先隊列實作dijkastra -天梯賽練習

L2-001. 緊急救援

作為一個城市的應急救援隊伍的負責人，你有一張特殊的全國地圖。在地圖上顯示有多個分散的城市和一些連接配接城市的快速道路。每個城市的救援隊數量和每一條連接配接兩個城市的快速道路長度都标在地圖上。當其他城市有緊急求助電話給你的時候，你的任務是帶領你的救援隊盡快趕往事發地，同時，一路上召集盡可能多的救援隊。

輸入格式：

輸入第一行給出4個正整數N、M、S、D，其中N（2<=N<=500）是城市的個數，順便假設城市的編号為0~(N-1)；M是快速道路的條數；S是出發地的城市編号；D是目的地的城市編号。第二行給出N個正整數，其中第i個數是第i個城市的救援隊的數目，數字間以空格分隔。随後的M行中，每行給出一條快速道路的資訊，分别是：城市1、城市2、快速道路的長度，中間用空格分開，數字均為整數且不超過500。輸入保證救援可行且最優解唯一。

輸出格式：

第一行輸出不同的最短路徑的條數和能夠召集的最多的救援隊數量。第二行輸出從S到D的路徑中經過的城市編号。數字間以空格分隔，輸出首尾不能有多餘空格。

輸入樣例：

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      

解題思路 借助輔助數組 now[i] 表示 到 i 點最多能集合多少人 num[i] 表示 到 i 點有多少種最短的路 在Dijkastra算法中更新兩者的值。 隻有長度相等的時候，才去考慮怎麼樣集結更多人，并且此時到這個點的方式又多出很多種，是以多加有個 if 判斷即可

循環實作代碼

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <stack>
#include <stdlib.h>
#include <map>

using namespace std;

const int maxn = 510;
const int INF = 0x3f3f3f3f;
int g[maxn][maxn];
int weight[maxn];
int d[maxn];
int num[maxn];///到目前結點最短路多少條
int now[maxn];///到目前節點最多的人數
int pre[maxn];
bool visit[maxn];
int n,m,s,de;


void disjk(){
    memset(d,INF,sizeof(d));
    memset(visit,0,sizeof(visit));
    d[s] = 0;
    num[s] = 1;
    now[s] = weight[s];
    while(1){
        int u = -1;
        ///從未選取的點中找一個離起點最近的點
        for(int i = 0; i < n; ++i){
            if(visit[i]) continue;
            if(u == -1 || d[i] < d[u])
                u = i;
        }
        if(u==-1) return;

        visit[u] = true;

        ///更新和這個點相接的點
        for(int i = 0;i < n; ++i){
            if(d[u]+g[u][i] < d[i]){///短為第一要素
                d[i] = d[u]+g[u][i];
                num[i] = num[u];
                now[i] = now[u]+weight[i];
                pre[i] = u;
            }

            ///如果長度相等,才考慮越多人越好
            else if(d[u]+g[u][i] == d[i]){
                num[i] += num[u];///通過這兩種達到i的方式各有num[i]和num[u]種，相加
                if(now[i] < now[u] + weight[i]){
                    now[i] = now[u] + weight[i];
                    pre[i] = u;
                }
            }
        }
    }
}


void dfs(int x){
    if(x == s) printf("%d",x);
    else{
        dfs(pre[x]);
        printf(" %d",x);
    }
}


int main(){
    scanf("%d%d%d%d",&n,&m,&s,&de);
    memset(g,INF,sizeof(g));
    int u,v,w;
    for(int i = 0; i < n; ++i) {scanf("%d",&weight[i]);}
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d",&u,&v,&w);
        g[u][v] = w;
        g[v][u] = w;
    }

    disjk();
    printf("%d %d\n",num[de],now[de]);
    dfs(de);
    return 0;
}
           

優先隊列實作代碼：

#include <cstring>
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <math.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 500+10;
typedef pair<int,int> P;

struct edge{
    int to ,cost;
};
vector <edge> G[maxn];
int cnt[maxn];///路條數
int num[maxn];///人數
int weight[maxn];
int dis[maxn];
int pre[maxn];
int s;
void disjk(int s){
    memset(cnt,0,sizeof(cnt));
    memset(dis,INF,sizeof(dis));
    priority_queue <P,vector<P>, greater<P> > que;
    dis[s] = 0;
    cnt[s] = 1;
    num[s] = weight[s];
    que.push(P(0,s));
    while(!que.empty()){
        P p = que.top();
        que.pop();
        int v = p.second, d = p.first;
        if(dis[v]<d) continue;
        for(int i = 0;i<G[v].size();++i){
            edge &e = G[v][i];
            int d2 = d+e.cost;
            if(d2 < dis[e.to]) {
                dis[e.to] = d2;
                pre[e.to] = v;
                cnt[e.to] = cnt[v];
                num[e.to] = num[v]+weight[e.to];
                que.push(P(dis[e.to],e.to));
            }else if( d2==dis[e.to]){
                cnt[e.to] += cnt[v];
                if(num[v]+weight[e.to]>num[e.to]){
                    num[e.to] = num[v]+weight[e.to];
                    pre[e.to] = v;
                }
            }
        }

    }
}

void dfs(int x){
    if(x == s) printf("%d",x);
    else{
        dfs(pre[x]);
        printf(" %d",x);
    }
}

int main(){
    int n,m,de;
    scanf("%d%d%d%d",&n,&m,&s,&de);
    int u,v,w;
    for(int i = 0; i < n; ++i) {scanf("%d",&weight[i]);}
    for(int i = 0; i < m; ++i){
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back((edge){v,w});
        G[v].push_back((edge){u,w});
    }
    disjk(s);
    printf("%d %d\n",cnt[de],num[de]);
    dfs(de);

    return 0;
}