admin管理员组

文章数量:1577819


Solution：

这道题的意思是给定起点和终点，求最短路。但还有一个要求，就是每个城市有救援队，我们要在求得最短路的情况下集结沿途尽可能多的救援队人数。
这道题的n值较小，直接dijkstra即可。

代码如下：

#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;

int visit[505],dis[505],mp[505][505];
int num[505];//记录最短路的条数
int p[505];//记录每个城市的救援队人数
int value[505];//记录到这个点为止可以获得的最大救援人数
int n,m;//n为城市个数，m为路径条数

void dijkstra(int s){
  for(int i=0;i<505;i++){
    visit[i]=0;
    num[i]=0;
    dis[i]=INF;
    value[i]=0;
  }

  dis[s]=0;
  num[s]=1;
  value[s]=p[s];
  for(int i=0;i<n;i++){
    int u=-1,min1=INF;
    for(int j=0;j<n;j++){
      if(dis[j]<min1&&visit[j]==0){
          min1=dis[j];
          u=j;
      }
    }
    if(u==-1){
      return;
    }
    visit[u]=1;
    for(int v=0;v<n;v++){
      if(visit[v]==0&&mp[u][v]!=INF){
        if(dis[v]>dis[u]+mp[u][v]){
            dis[v]=dis[u]+mp[u][v];
            num[v]=num[u];
            value[v]=value[u]+p[v];
        }else if(dis[v]==dis[u]+mp[u][v]){
            num[v]=num[v]+num[u];
            if(value[v]<value[u]+p[v]){
              value[v]=value[u]+p[v];
            }
        }
      }
    }
  }
}

int main(){
  int start,end1;
  cin>>n>>m>>start>>end1;//读入结点数、边数、起点、终点
  for(int i=0;i<505;i++){//初始化
    for(int j=0;j<505;j++){
        mp[i][j]=INF;
    }
  }
  for(int i=0;i<n;i++){
    cin>>p[i];
  }
  int a,b,len;
  for(int i=0;i<m;i++){
    cin>>a>>b>>len;
    mp[a][b]=mp[b][a]=len;
  }
  dijkstra(start);
  cout<<num[end1]<<' '<<value[end1];
  return 0;
}

本文标签： PATEmergencyDijkstra单源

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