作為一個(gè)城市的應(yīng)急救援隊(duì)伍的負(fù)責(zé)人，你有一張?zhí)厥獾娜珖貓D。在地圖上顯示有多個(gè)分散的城市和一些連接城市的快速道路。每個(gè)城市的救援隊(duì)數(shù)量和每一條連接兩個(gè)城市的快速道路長度都標(biāo)在地圖上。當(dāng)其他城市有緊急求助電話給你的時(shí)候，你的任務(wù)是帶領(lǐng)你的救援隊(duì)盡快趕往事發(fā)地，同時(shí)，一路上召集盡可能多的救援隊(duì)。

輸入格式:
輸入第一行給出4個(gè)正整數(shù)N、M、S、D，其中N（2≤N≤500）是城市的個(gè)數(shù)，順便假設(shè)城市的編號為0 ~ (N?1)；M是快速道路的條數(shù)；S是出發(fā)地的城市編號；D是目的地的城市編號。

第二行給出N個(gè)正整數(shù)，其中第i個(gè)數(shù)是第i個(gè)城市的救援隊(duì)的數(shù)目，數(shù)字間以空格分隔。隨后的M行中，每行給出一條快速道路的信息，分別是：城市1、城市2、快速道路的長度，中間用空格分開，數(shù)字均為整數(shù)且不超過500。輸入保證救援可行且最優(yōu)解唯一。

輸出格式:
第一行輸出最短路徑的條數(shù)和能夠召集的最多的救援隊(duì)數(shù)量。第二行輸出從S到D的路徑中經(jīng)過的城市編號。數(shù)字間以空格分隔，輸出結(jié)尾不能有多余空格。

輸入樣例:
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

主要思想是：裸的Dijkstra，問題是如何計(jì)算最短路徑條數(shù)，其實(shí)遵循這樣兩條原則：

如果A到B只有一條路可以走，那么到B的路條數(shù)就是到A的條數(shù)

如果不是一條路，就把所有的路加起來。

#include <bits/stdc++.h> using namespace std; int Map[501][501]; //記錄圖的邊信息 int peo[501]; //截止走到此處積累的人數(shù) int Count[501]; //走到此處的方法數(shù) int vis[501]; //此點(diǎn)是否已經(jīng)走過 int Path[501]; //記錄路徑 int dist[501]; int ph[501]; //people here:此點(diǎn)的人數(shù) int n,s,d; void path(int d); int main() {int m;cin>>n>>m>>s>>d;for (int i=0;i<n;i++)//初始化 {Path[i]=-1;dist[i]=1000000;cin>>ph[i];for (int j=0;j<n;j++){Map[i][j]=1000000;}}dist[s]=0; //起點(diǎn)到起點(diǎn)的距離是0 Count[s]=1; //起點(diǎn)到起點(diǎn)一種方式 vis[s]=1; //將起點(diǎn)放入集合 peo[s]=ph[s]; //走到起點(diǎn)的人數(shù)就是起點(diǎn)的人數(shù) int c1,c2,len; //輸入使用 for (int i=0;i<m;i++) //輸入邊的信息 {cin>>c1>>c2>>len;Map[c1][c2]=len;Map[c2][c1]=len;}for (int i=0;i<n;i++){if (Map[s][i]!=1000000){dist[i]=Map[s][i];}} //初始化完成 int min=s,minf; //min存放最小值下標(biāo)，minf存放最小值 for (int i=1;i<n;i++) //只需要循環(huán)n-1次，因?yàn)槊看螘暨x一個(gè)最小值，起點(diǎn)已經(jīng)進(jìn)入集合 {if (i==1){minf=dist[s];}else{minf=1000000;}for (int j=0;j<n;j++){if (!vis[j]&&dist[j]<minf) //挑選最小值 {min=j;minf=dist[j];}}vis[min]=1; //最小值放入集合for (int j=0;j<n;j++){if (vis[j]==0&&Map[min][j]!=1000000&&dist[min]+Map[min][j]<dist[j])//需要更新 {dist[j]=dist[min]+Map[min][j];Path[j]=min;Count[j]=Count[min]; //直線走過來，這點(diǎn)到達(dá)的方式和前驅(qū)相同peo[j]=peo[min]+ph[j]; //人手積累 }else if (vis[j]==0&&Map[min][j]!=1000000&&dist[min]+Map[min][j]==dist[j])//相等，需要看人手{Count[j]+=Count[min]; //不管怎樣，來著的方法要加1if (peo[min]+ph[j]>peo[j])//這條道路搖人更多 {peo[j]=peo[min]+ph[j];Path[j]=min; //換線 }}}}printf("%d %d\n",Count[d],peo[d]);path(d);printf("%d",d);return 0; }void path(int d) {if(Path[d] != -1) {path(Path[d]);printf("%d ", Path[d]);} }

總結(jié)

以上是生活随笔為你收集整理的7-2 城市间紧急救援 (25 分)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。