題目描述

有一個郵遞員要送東西，郵局在節點?1。他總共要送?n?1?樣東西，其目的地分別是節點?2?到節點?n。由于這個城市的交通比較繁忙，因此所有的道路都是單行的，共有?m?條道路。這個郵遞員每次只能帶一樣東西，并且運送每件物品過后必須返回郵局。求送完這?n?1?樣東西并且最終回到郵局最少需要的時間。

輸入格式

第一行包括兩個整數，n?和?m，表示城市的節點數量和道路數量。

第二行到第?(m+1)?行，每行三個整數，u,v,w，表示從?u?到?v?有一條通過時間為?w?的道路。

輸出格式

輸出僅一行，包含一個整數，為最少需要的時間。

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int N=1010;
int n,m;
int dis[N*2];
void dij(vector<vector<pii>> &g,int start){priority_queue<pii,vector<pii>,greater<pii>> q;dis[start]=0;q.push({dis[start],start});while(!q.empty()){int u=q.top().second;int d=q.top().first;q.pop();if(d>dis[u]) continue;for(auto & x:g[u]){int v=x.first,w=x.second;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;q.push({dis[v],v});//cout<<"??1";}}}
}
int main(){cin>>n>>m;vector<vector<pii>> gra(2*n+1);for(int i=1;i<=m;++i){int a,b,c;scanf("%d%d%d",&a,&b,&c);gra[a].push_back({b,c});gra[b+n].push_back({a+n,c});}int ans=0;for(int i=1;i<=2*n;++i) dis[i]=INF;dij(gra,1);for(int i=2;i<=n;++i){ans+=dis[i];//cout<<dis[i]<<" ";} dij(gra,1+n);for(int i=n+2;i<=n<<1;++i) ans+=dis[i];cout<<ans<<endl;return 0;
}