admin管理员组

文章数量:1577827

1003 Emergency (25 分)


题解：用的dijkstra,注意输出的要求是最短路径的数量和最短路径上最大的消防员数量。一定要注意第一个输出的是：最短路径的数量！！！（我一开始以为是最短路的长度，然后又以为是最短路中经过几个点，最后再看一遍题目发现是最短路的数量。）

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1e5+10;
const int mod=100000007;
int g[510][510];
int a[510];
int n,m,st,ed;
bool sta[510];
int sum[510];
int dis[510];
int ct[510];
int main(){
    cin>>n>>m>>st>>ed;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    memset(g,0x3f,sizeof g);
    for(int i=0;i<m;i++){
        int x,y,c;
        cin>>x>>y>>c;
        g[x][y]=min(g[x][y],c);
        g[y][x]=min(g[y][x],c);
    }
    memset(dis,0x3f,sizeof dis);
    dis[st]=0;
    memset(sum,0,sizeof sum);
    sum[st]=a[st];
    memset(sta,0,sizeof sta);
    ct[st]=1;
    for(int i=1;i<n;i++){
        int t=-1;
        for(int j=0;j<n;j++){
            if(!sta[j]&&(t==-1||dis[t]>dis[j])){
                t=j;
            }
        }
        sta[t]=1;
        for(int j=0;j<n;j++){
            if(!sta[j]&&dis[j]>dis[t]+g[t][j]){
                dis[j]=dis[t]+g[t][j];
                sum[j]=a[j]+sum[t];
                ct[j]=ct[t];
            }else if(!sta[j]&&dis[j]==(dis[t]+g[t][j])){
                if(sum[j]<a[j]+sum[t]){
                    sum[j]=a[j]+sum[t];
                }
                ct[j]+=ct[t];
            }
        }
    }
    cout<<ct[ed]<<" "<<sum[ed];
    return 0;
}

本文标签： PATEmergency

版权声明：本文标题：PAT 甲级 1003 Emergency (25 分) 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/dongtai/1727823123a1131961.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。