PTA7-12 城市間緊急救援 (25 分)
關于這個題呢，我當時也想了很久沒有一點頭緒，所以，菜雞的我一如既往的打開了CSDN(手動滑稽)，我看了很多大佬的寫法，最普遍的應該就是dijkstra+dp了，于是，在眾多大佬的代碼熏陶下，我琢磨出了比較簡單的寫法，也不能說簡單，也就是代碼可讀性高一點而已，小白寫文，如有錯誤還望多多諒解！
輸入格式:
輸入第一行給出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
我就用注釋來解釋吧
//dijstra+dp
#include "bits/stdc++.h"
using namespace std;
int ma[501][501],peo[501],Count[501],vis[501],path[501],dist[501],ph[501];
//ma[501][501]表示地圖,peo[501]表示拉的人數,Count[501]表示路的條數
//vis[501]標記點,path[501]記錄路徑,dist[501]最短距離,ph[501]每個城市的人數
int n,m,s,d;
void ath(int d)//列印路徑
{
if(path[d]!=-1)
{
ath(path[d]);
cout<<path[d]<<' ';
}
}
int main()
{
cin>>n>>m>>s>>d;
memset(ma,0x3f,sizeof(ma));//圖max
memset(dist,0x3f,sizeof(dist));//點距max
memset(path,-1,sizeof(path));//記錄路徑
memset(Count,1,sizeof(Count));//道路條數
for(int i=0;i<n;i++) cin>>ph[i];
//初始化...
dist[s]=0;
Count[s]=1;
//vis[s]=1;
peo[s]=ph[s];
while(m--)//把路存到地圖上
{
int j,k,l;
cin>>j>>k>>l;
ma[j][k]=ma[k][j]=l;
}
//接下來就是重頭戲dijstra了
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=0;j<n;j++)//找距離最短的點
{
if((t==-1||dist[j]<dist[t])&&!vis[j]) t=j;
}
if(t==-1) break;//所有點都找過了
vis[t]=1;//標記該點
for(int j=0;j<n;j++)
{
if(dist[t]+ma[t][j]<dist[j])//如果路徑更短的話（又名松弛）
{
dist[j]=dist[t]+ma[t][j];//更新距離
path[j]=t;//記錄路徑
Count[j]=Count[t];//記錄路數
peo[j]=ph[j]+peo[t];//記錄總人數
}
else if(dist[t]+ma[t][j]==dist[j])//如果一樣長
{
Count[j]+=Count[t];//路數就要增加
if(peo[t]+ph[j]>peo[j])//如果人數更多
{
peo[j]=peo[t]+ph[j];//拉人
path[j]=t;//記錄路徑
}
}
}
}
cout<<Count[d]<<' '<<peo[d]<<endl;
ath(d);
cout<<d;
}
就這樣王子和公主過上了幸福快樂的生活 我們就成功解決了這個題！
cheer！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/274132.html
標籤：其他
下一篇：八皇后問題詳解