P1629 邮递员送信

P1629 邮递员送信 - 洛谷

题目描述

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

输入格式

第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。
第二行到第 (m+1) 行，每行三个整数，u,v,w，表示从 u 到 v 有一条通过时间为 w 的道路。

输出格式

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

输入输出样例

输入 #1

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

输出 #1

83

说明 / 提示

对于 30% 的数据，1≤n≤200。
对于 100% 的数据，1≤n≤103，1≤m≤105，1≤u,v≤n，1≤w≤104，输入保证任意两点都能互相到达。

思路：
注意2->1的距离，再反向建立图中，是1->2的距离，所以在反向建立图中，1是起点。

代码：
 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII; 
const int MAXN = 10010;   
const int INF = 0x3f3f3f3f;
vector<PII> ori[MAXN];//原图 
vector<PII> rever[MAXN];//反向图 
int dist1[MAXN];//原图的最短路径 
int dist2[MAXN];//反向图的最短路径 
bool visited[MAXN];
void dijkstra(int start, vector<PII> adj[], int dist[]) 
{
    memset(dist, 0x3f, sizeof(int) * MAXN);
    memset(visited, false, sizeof(visited));
    
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    
    dist[start] = 0;
    pq.push(PII(0, start));
    
    while (!pq.empty()) 
	{
        auto temp = pq.top();  
        pq.pop();
        int currentDist = temp.first; 
        int u = temp.second;  
        
        if (visited[u]) continue;
        visited[u] = true;
        
        for (auto e : adj[u]) 
		{
            int v = e.first;  
            int w = e.second;
            if (dist[v] > dist[u] + w) 
			{
                dist[v] = dist[u] + w;
                pq.push(PII(dist[v], v));
            }
        }
    }
}
int main() 
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i) 
    {
        int u, v, w;
        cin >> u >> v >> w;
        ori[u].push_back({v, w});
        rever[v].push_back({u, w});
    }
    dijkstra(1, ori, dist1);
    dijkstra(1, rever, dist2);
    int total = 0;
    for (int i = 2; i <= n; ++i) 
    {
        total += dist1[i] + dist2[i];
    }
    cout << total << endl;
    
    return 0;
}