立志用最少的代碼做最高效的表達(dá)

---

作為一個(gè)城市的應(yīng)急救援隊(duì)伍的負(fù)責(zé)人，你有一張?zhí)厥獾娜珖?guó)地圖。在地圖上顯示有多個(gè)分散的城市和一些連接城市的快速道路。每個(gè)城市的救援隊(duì)數(shù)量和每一條連接兩個(gè)城市的快速道路長(zhǎng)度都標(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è)城市的編號(hào)為0 ~ (N?1)；M是快速道路的條數(shù)；S是出發(fā)地的城市編號(hào)；D是目的地的城市編號(hào)。

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

輸出格式:
第一行輸出最短路徑的條數(shù)和能夠召集的最多的救援隊(duì)數(shù)量。第二行輸出從S到D的路徑中經(jīng)過(guò)的城市編號(hào)。數(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

---

最開(kāi)始用dfs做，最后一個(gè)測(cè)試點(diǎn)超時(shí)。改為dijkstra，滿分。

時(shí)間規(guī)模計(jì)算：dijkstra的時(shí)間復(fù)雜度為O(n2)，地圖最大規(guī)模為500，500*500=25w，也就是最大規(guī)模為25w， 100ms大約運(yùn)行100w的數(shù)據(jù)，因此可以AC

---

#include<iostream> #include<cstdio> #include<cstring> #include<stack>using namespace std; const int inf = 0x3f3f3f3f; const int maxn = 510; //通過(guò)path存儲(chǔ)，最終的結(jié)果一定是最優(yōu)的 int G[maxn][maxn]; //地圖 int num_p[maxn]; //每個(gè)城市救火隊(duì)數(shù)量 int vis[maxn]; //每個(gè)點(diǎn)是否遍歷過(guò) int dist[maxn]; //起點(diǎn)距離各個(gè)點(diǎn)的最短距離 int sum_p[maxn]; //從出發(fā)點(diǎn)到城市i的救援隊(duì)目的和 int path[maxn]; //以第i個(gè)節(jié)點(diǎn)為終點(diǎn)的最短路徑的前一個(gè)節(jié)點(diǎn)的編號(hào) int num[maxn]; //出發(fā)點(diǎn)到城市i的最短路徑條數(shù) int n, m, sta, fin; void dijkstra() {//初始化操作 fill(dist, dist + 510, inf);dist[sta] = 0;sum_p[sta] = num_p[sta];num[sta] = 1; //最短路徑條數(shù)為1 path[sta] = -1; //初始節(jié)點(diǎn)為-1 for(int i = 0; i < n; i++) {int u = -1, minx = inf;for(int j = 0; j < n; j++) {if(vis[j] == 0 && minx > dist[j]) { //找最短路徑 u = j;minx = dist[j];}}if(u == -1) break; //不連通vis[u] = 1; //設(shè)置為已訪問(wèn)for(int j = 0; j < n; j++) {//如果經(jīng)過(guò)u再到j(luò)更短，則更新 if(vis[j] == 0 && dist[u] + G[u][j] < dist[j] ) {dist[j] = dist[u] + G[u][j];num[j] = num[u]; //更新最短路徑條數(shù)sum_p[j] = sum_p[u] + num_p[j]; //救援隊(duì)數(shù)目增加path[j] = u; //經(jīng)過(guò)u點(diǎn)再到j(luò)點(diǎn) } else if(dist[u] + G[u][j] == dist[j]) {num[j] = num[j] + num[u];if(sum_p[u] + num_p[j] > sum_p[j]) {sum_p[j] = sum_p[u] + num_p[j];path[j] = u;} }} } }int main() {cin >> n >> m >> sta >> fin; for(int i = 0; i < n; i++) cin >> num_p[i];//1、初始化圖for(int i = 0; i < n; i++) for(int j = 0; j < n; j++)G[i][j] = inf;//2、輸入 for(int i = 0; i < m; i++) {int x, y, v; cin >> x >> y >> v;G[x][y] = G[y][x] = v; }//3、更新distfor(int i = 0; i < n; i++) {dist[i] = G[sta][i];} //4、dijkstradijkstra(); cout << num[fin] << ' ' << sum_p[fin] << '\n';stack<int> ss;ss.push(fin);while(path[fin] != 0) {ss.push(path[fin]);fin = path[fin];}cout << sta;while(!ss.empty()) {cout << ' ' << ss.top();ss.pop(); }return 0; }

---

耗時(shí)：

---

???????——弱小和無(wú)知不是生存的障礙，傲慢才是。

總結(jié)

以上是生活随笔為你收集整理的城市间紧急救援 (25 分)【dijkstra模板 超时原因】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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