题目链接

最短路——邮递员送信（dijkstra）

题目描述

有一个邮递员要送东西，邮局在节点 1。他总共要送 n-1 样东西，其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。

第二行到第 (m+1) 行，每行三个整数，u,v,w，表示从 u 到 v 有一条通过时间为 w 的道路。

输出格式

输出仅一行，包含一个整数，为最少需要的时间。

输入输出样例

输入

5 10 2 3 5 1 5 5 3 5 6 1 2 8 1 3 8 5 3 4 4 1 8 4 5 3 3 5 6 5 4 2

输出

83

#include<bits/stdc++.h> #define pii pair<int,int> using namespace std; const int maxn=1e5+5; const int inf=0x3f3f3f3f; int n,m,u,v,w; struct node{ int to,len; }; vector<node> f[maxn]; int dis[maxn],vis[maxn]; void dijkstra(int t) { memset(dis,inf,sizeof(dis)); memset(vis,0,sizeof(vis)); priority_queue<pii,vector<pii>,greater<pii> > q; dis[t]=0; q.push(pii(0,t)); while(!q.empty()){ pii x=q.top(); q.pop(); int tt=x.second; if(vis[tt]){ continue; } vis[tt]=1; for(int i=0;i<f[tt].size();i++){ node a=f[tt][i]; if(dis[a.to]>dis[tt]+a.len){ dis[a.to]=dis[tt]+a.len; q.push(pii(dis[a.to],a.to)); } } } } int main() { cin>>n>>m; for(int i=0;i<m;i++){ cin>>u>>v>>w; f[u].push_back({v,w}); f[v+n].push_back({u+n,w}); } dijkstra(1); // 正向 int sum=0; for(int i=2;i<=n;i++){ sum+=dis[i]; } dijkstra(1+n); // 反向 for(int i=2+n;i<=n*2;i++){ sum+=dis[i]; } cout<<sum<<endl; return 0; }