当前位置:   article > 正文

PTA 紧急救援 /// dijkstra 最短路数 输出路径

dijkstra输出路径 pta

题目大意:

给定 n m s t ;表示n个点编号为0~n-1 m条边 起点s终点t

接下来一行给定n个数;表示第i个点的救援队数量

接下来m行给定u v w;表示点u到点v有一条长度为w的边

 

求从s到t的最短路有几条

一条路上可以集合的救援队最多有多少

输出路径

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long
#define inc(i,j,k) for(int i=j;i<=k;i++)
#define dec(i,j,k) for(int i=j;i>=k;i--)
#define gcd(i,j) __gcd(i,j)
#define mem(i,j) memset(i,j,sizeof(i))
const int N=2e5+5;
const int mod=1e9+7;

int n,m,s,t;
int V[N];
struct NODE{ int to,len; };
vector <NODE> G[N];
int dis[N], num[N];
int sumV[N], pre[N];
bool vis[N];

int main()
{
    while(~scanf("%d%d%d%d",&n,&m,&s,&t)) {
        inc(i,0,n-1) scanf("%d",&V[i]);
        inc(i,0,n-1) G[i].clear();
        while(m--) {
            int u,v,w; scanf("%d%d%d",&u,&v,&w);
            G[u].push_back({v,w});
            G[v].push_back({u,w});
        }
        mem(sumV,0); sumV[s]=V[s]; // 到i点的最短路可集合sumV[i]救援队
        mem(dis,INF); dis[s]=0; // 到i点的最短路长度为dis[i]
        mem(num,0); num[s]=1; // 到i点的最短路有num[i]条
        mem(pre,-1); mem(vis,0); // pre记录路径前驱 vis标记走过
        while(1) {
            int u, mini=INF;
            inc(i,0,n-1)
                if(!vis[i] && dis[i]<mini)
                    mini=dis[i], u=i;
            if(mini==INF) break; 
            vis[u]=1;
            int all=G[u].size();
            inc(i,0,all-1) {
                NODE v=G[u][i];
                if(vis[v.to]) continue;
                if(dis[v.to]>dis[u]+v.len) {
                    sumV[v.to]=sumV[u]+V[v.to];
                    dis[v.to]=dis[u]+v.len;
                    num[v.to]=num[u];
                    pre[v.to]=u;
                } else if(dis[v.to]==dis[u]+v.len) {
                    num[v.to]+=num[u];
                    if(sumV[v.to]<sumV[u]+V[v.to]) {
                        sumV[v.to]=sumV[u]+V[v.to],
                        pre[v.to]=u;
                    }
                }
            }
        }
        printf("%d %d\n",num[t],sumV[t]);
        stack <int> s; int c=0;
        while(t!=-1) s.push(t), t=pre[t], c++;
        while(!s.empty()) {
            printf("%d",s.top()); s.pop();
            if(--c==0) printf("\n");
            else printf(" ");
        }
    }

    return 0;
}
View Code

 

转载于:https://www.cnblogs.com/zquzjx/p/10571356.html

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/714625
推荐阅读
相关标签
  

闽ICP备14008679号