2021.3.10
題目背景
墨家家主發(fā)出召集令，所有弟子得迅速到指定地點集合。

題目描述
給定一張地圖，含有n個地點(n<=10000)，地點從1開始編號，地圖上還含有m條單向路(m<=100000)連接著這些地點，墨家家主在1號位置，其余n-1個地點都有一個墨家弟子，通過一條路，從一個地點到另外一個地點需要花費一定的金錢， 第i條路需要花費$w_i$（$w_i$<=10000)

問：所有弟子到墨家家主所在位置至少需要花費多少金錢。

輸入格式
第一行，兩個整數(shù)，分別是n和m，代表n個地點和m條單向路；
接下來m行，三個整數(shù)u，v，w，分別代表這一條路的起點、終點和花費的金錢。

輸出格式
一個整數(shù)，代表至少需要花費的金錢。

輸入輸出樣例
輸入
5 10
1 5 3
2 1 2
2 3 7
3 2 7
3 2 8
3 4 10
4 1 10
4 5 9
5 3 10
5 1 1
輸出
22
說明/提示
對于25%，n<=10, m<=100；
對于50%，n<=100, m<=1000；
對于75%，n<=1000, m<=10000；
對于100%，n<=10000,m<=100000,w_i<=10000。

時限:1.0s
內(nèi)存:500MB

代碼如下：

#include <iostream> #include <cstring> using namespace std; const int N = 10010; const int MAXCOST = 100100; int vertexnum, arcnum; int graph[N][N];int dijkstra(int graph[][N], int n, int v) {bool vis[N];int dis[N];memset(vis, 0, sizeof(vis));for (int i = 1; i <= n; i++)dis[i] = graph[v][i];vis[v] = true;for (int i = 1; i <= n - 1; i++) {int minx = MAXCOST;int minid = 0;for (int j = 1; j <= n; j++) {if (vis[j] == 0 && dis[j] < minx) {minx = dis[j];minid = j;}}vis[minid] = true;for (int k = 1; k <= n; k++) {if (graph[minid][k] < MAXCOST)if (dis[k] > dis[minid] + graph[minid][k]) {dis[k] = dis[minid] + graph[minid][k];}}}return dis[1]; }int main() {cin >> vertexnum >> arcnum;for (int i = 1; i <= vertexnum; i++)for (int j = 1; j <= vertexnum; j++)if (i == j)graph[i][j] = 0;elsegraph[i][j] = MAXCOST;for (int i = 1; i <= arcnum; i++) {int a, b, w;cin >> a >> b >> w;if (graph[a][b] > w)graph[a][b] = w;}int sum = 0;for (int i = 2; i <= vertexnum; i++) {int c = dijkstra(graph, vertexnum, i);sum += c;}cout << sum << endl;return 0; }

本人水平有限，采用了鄰接矩陣的Dijkstra算法，只能拿50分…，還望有大神能給予幫助。

哈哈哈哈哈，突然想到了怎么解了，發(fā)現(xiàn)自己太笨了，這題求的是所有其他點(墨家弟子)到起點(墨家家主)的距離之和，我居然用dijkstra求每一個點到起點的位置，但是其實，我們只要將題意轉(zhuǎn)換，變成墨家家主到其他所有點的距離之和，就變成了用一次dijkstra算法就行了，只要輸入的時候，原本方向是a到b的，我們就改成b到a，最后用一次dijkstra算法就行了。

AC代碼如下：

#include <iostream> #include <cstring> using namespace std; const int N = 10010; const int MAXCOST = 100100; int vertexnum, arcnum; int graph[N][N]; bool vis[N]; int dijkstra(int graph[][N], int n, int v) {int dis[N];for (int i = 1; i <= n; i++)dis[i] = graph[v][i];vis[v] = true;for (int i = 1; i <= n - 1; i++) {int minx = MAXCOST;int minid = 0;for (int j = 1; j <= n; j++) {if (vis[j] == 0 && dis[j] < minx) {minx = dis[j];minid = j;}}vis[minid] = true;for (int k = 1; k <= n; k++) {if (graph[minid][k] < MAXCOST)if (dis[k] > dis[minid] + graph[minid][k]) {dis[k] = dis[minid] + graph[minid][k];}}}int sum = 0;for (int i = 1; i <= n; i++) {sum += dis[i];}return sum; }int main() {cin >> vertexnum >> arcnum;for (int i = 1; i <= vertexnum; i++)for (int j = 1; j <= vertexnum; j++)if (i == j)graph[i][j] = 0;elsegraph[i][j] = MAXCOST;for (int i = 1; i <= arcnum; i++) {int a, b, w;cin >> a >> b >> w;if (graph[b][a] > w)graph[b][a] = w;}int sum = 0;cout << dijkstra(graph, vertexnum, 1);return 0; }

2021.3.25更新
好像才隔了15天。
學會了鄰接表實現(xiàn)的dijkstra算法，然后再來ac一下這題！！！

代碼如下：

#include <iostream> #include <vector> #include <queue> #include <string> using namespace std; const int N = 10010; bool done[N]; int dis[N]; const int INF = 1 << 30; int n, m;struct edge {int from;int to;int w; };struct node {int id;int dis;friend bool operator<(const node &a, const node &b) {return a.dis > b.dis;} };vector<edge>e[N];void dijkstra() {priority_queue<node>q;int s = 1;memset(done, 0, sizeof(done));for (int i = 1; i <= n; i++)dis[i] = INF;dis[s] = 0;q.push({s, dis[s]});while (q.size()) {node t = q.top();q.pop();if (done[t.id])continue;for (int i = 0; i < e[t.id].size(); i++) {edge y = e[t.id][i];if (done[y.to])continue;if (dis[y.to] > y.w + t.dis) {dis[y.to] = y.w + t.dis;q.push({y.to, dis[y.to]});}}}int ans = 0;for (int i = 1; i <= n; i++) {ans += dis[i];}cout << ans << endl; }int main() {cin >> n >> m;while (m--) {int a, b, c;cin >> a >> b >> c;e[b].push_back({b, a, c});}dijkstra();return 0; }

總結

以上是生活随笔為你收集整理的[召集令]-Dijkstra的单源最短路径算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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