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

輸入格式:

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

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

輸出格式:

第一行輸出最短路徑的條數(shù)和能夠召集的最多的救援隊數(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

首先:最簡單的就是無腦DFS搜索全部情況返回最優(yōu)解?

#include<bits/stdc++.h>
using namespace std;
const int maxn = 510;
int N, M, S, D, A, B, C, road = 0, love, mind = 1 << 20;//路徑 救援?dāng)?shù)
vector<int>sove(maxn);
int MAP[maxn][maxn];
deque<int>ans;
deque<int>s;
bool vis[maxn][maxn];
void DFS(int str, int end, int d, int sum)//起始 結(jié)尾 路徑 救援?dāng)?shù)
{if (str == end && mind >= d){ //達(dá)到目的地 if(mind > d){road = 0;ans = s;mind = d;love = sum;}else if(d == mind && love < sum){love = sum;ans = s;}road++;return;}else if(str == end)return;for (int i = 0; i < N; i++){if (MAP[str][i] && !vis[str][i]){vis[str][i] = true;s.push_back(i);DFS(i, end, d + MAP[str][i], sum + sove[i]);vis[str][i] = false;s.pop_back();}}
}int main()
{cin >> N >> M >> S >> D;for (int i = 0; i < N; i++){cin >> sove[i];}for (int i = 0; i < M; i++){cin >> A >> B >> C;MAP[A][B] = MAP[B][A] = C;}DFS(S, D, 0, sove[S]);cout << road << " " << love << endl << S;while (!ans.empty()){cout << " " << ans.front();ans.pop_front();}return 0;
}

但是缺陷也是比較明顯的,如果圖中各節(jié)點的聯(lián)通網(wǎng)十分密集的話,那我們遞歸的深度就很容易導(dǎo)致系統(tǒng)棧被壓爆,從而得不出答案

?那么就得涉及到最短路徑算法了,常見的Dijkstra或者Floyd

當(dāng)然也有Bellman 和 SPFA但是對于這題效果不如dijkstra

簡單的科普Dijkstra和Floyd算法

最短路徑（Dijkstra算法和Floyd算法）_法蘇ovo的博客-CSDN博客

基于Floyd大多是處理任意倆點最短路徑(并且效率較低)而我們這題側(cè)重于單源路徑,就采用Dijikstra進(jìn)行解題

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 510;
int N, M, S, D, A, B, len;
vector<int>p(maxn), pre(maxn, -1), num(maxn), per(maxn), dis(maxn, INT_MAX);
// 各點的救援隊數(shù)量  前置結(jié)點  從起點到該點的最短路數(shù)量 從起點到該點最短路的救援隊數(shù)量 從起點到該點的最短距離 
bool vis[maxn];
struct edge
{int to, len;edge(int a, int b) : to(a), len(b) {};
};
vector<edge>e[maxn];
struct q_node
{int id, dis;q_node(int a, int b) :id(a), dis(b) {};bool operator< (const q_node& s)const{return dis > s.dis;}
};
void printf_path(int x)
{if (pre[x] == -1) return;printf_path(pre[x]);printf(" %d", x);
}
void dijkstra()
{dis[S] = 0, num[S] = 1, per[S] = p[S];priority_queue<q_node>Q;Q.emplace(S, dis[S]);while (!Q.empty()){auto x = Q.top();Q.pop();if (vis[x.id])continue;vis[x.id] = true;for (int i = 0; i < e[x.id].size(); i++){auto y = e[x.id][i];//枚舉鄰居if (dis[y.to] == dis[x.id] + y.len)num[y.to] += num[x.id];if (dis[y.to] > dis[x.id] + y.len)num[y.to] = num[x.id];if ((dis[y.to] == dis[x.id] + y.len && per[y.to] < per[x.id] + p[y.to]) || dis[y.to] > dis[x.id] + y.len){per[y.to] = per[x.id] + p[y.to];pre[y.to] = x.id;dis[y.to] = dis[x.id] + y.len;Q.emplace(y.to, dis[y.to]);}}}
}
int main()
{cin >> N >> M >> S >> D;for (int i = 0; i < N; i++)cin >> p[i];while (M--){cin >> A >> B >> len;e[A].emplace_back(B, len);e[B].emplace_back(A, len);}dijkstra();cout << num[D] << " " << per[D] << endl << S;printf_path(D);return 0;
}

Dijkstra算法練習(xí)

公交線路 (nowcoder.com)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n,m,s,t,A,B,len;
struct edge
{int form,to,len;edge(int a,int b,int c) : form(a),to(b),len(c){};
};
vector<edge>e[maxn];
vector<int>dis(maxn,0x3f3f3f3f),pre(maxn);
bool vis[maxn];
struct q_node
{int id,dis;q_node(int a,int b):id(a),dis(b){};bool operator < (const q_node& s)const{return dis > s.dis;}
};
void dijkstra()
{dis[s] = 0;priority_queue<q_node>Q;Q.emplace(s,dis[s]);while(!Q.empty()){auto x = Q.top();Q.pop();if(vis[x.id])continue;vis[x.id] = true;for(int i = 0;i < e[x.id].size();i++){auto y = e[x.id][i];if(vis[y.to])continue;if(dis[y.to] > x.dis + y.len){dis[y.to] = x.dis + y.len;pre[y.to] = x.id;Q.emplace(y.to,dis[y.to]);}}}
}
int main()
{cin.tie(0)->sync_with_stdio(false);cin >> n >> m >> s >> t;while(m--){cin >> A >> B >> len;e[A].emplace_back(A,B,len);e[B].emplace_back(B,A,len);}dijkstra();dis[t] == 0x3f3f3f3f ? cout << -1 << endl : cout << dis[t] << endl;return 0;
}