苹果运输

苹果运输"/>

苹果运输

苹果运输

题目描述:

Bessie将要把两箱脆脆的红苹果送给她的两个朋友 。当然，像常见的图一样有 C (1 <= C <= 200,000)条牛径连接着P (1<= P <= 100,000)个牧场（为了方便起见，标号1..p）,牛径是双向的，每条路都有一个长度。而且我们总是能从一个牧场到另外一个牧场。每条牛径连接两个不同的牧场 P1_i (1 <= P1_i <= P) 和P2_i (1

<= P2_i <= P) ，长度为 D_i。 所有路径长度之和不超过2,000,000,000。

Bessie从牧场PB (1 <= PB <= P)出发，求Bessie把苹果送给她的两个朋友（分别在 PA1 (1 <= PA1 <= P)和PA2 (1 <= PA2 <= P)）所需走的最短路程，（无所谓先把苹果送给谁）。这三个牧场都是不同的。

考虑下面这个例子，括号内的是牧场编号，其余是路径长度。

                3        2       2

           [1]-----[2]------[3]-----[4]

             \     / \              /

             7\   /4  \3           /2

               \ /     \          /

               [5]-----[6]------[7]

                    1       2 

如果 Bessie从[5]出发，把苹果送到[1]和[4]，她走的路径是这样的 

      5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1* 

总长 12.

输入格式:

* Line 1: Line 1 包含五个用空格分开的整数 C, P, PB,PA1, 和 PA2

* Lines 2..C+1: Line i+1 描述牛径 i，其端点 P1_i, P2_i，和长度 D_i

输出格式:

* Line 1: Bessie所需走的最小路程。

样例输入:

9 7 5 1 4
5 1 7
6 7 2
4 7 2
5 6 1
5 2 4
4 3 2
1 2 3
3 2 2
2 6 3

样例输出:

12

时间限制:1000ms
空间限制:256MByte

#include<bits/stdc++.h>
using namespace std;
struct enode{int y, z;enode(int y1, int z1) : y(y1), z(z1) {}
};vector<enode> e[200005];struct node{int dis, v;node(int x1, int y1) : dis(x1), v(y1) {}bool operator < (const node &a) const{return dis > a.dis;}
};priority_queue<node> q;
int dis[100005];
bool vis[100005];int main()
{int c, p, pb, pa1, pa2, x, y, z, v, t;cin>>c>>p>>pb>>pa1>>pa2;for(int i = 1; i <= c; i++){cin>>x>>y>>z;e[x].push_back(enode(y, z));e[y].push_back(enode(x, z));}memset(dis, 0x3f3f3f3f, sizeof(dis));dis[pb] = 0;q.push(node(0, pb));while(!q.empty()){v = q.top().v;q.pop();if(vis[v]) continue;vis[v] = 1;for(int i = 0; i < e[v].size(); i++)if(dis[v] + e[v][i].z < dis[e[v][i].y]){dis[e[v][i].y] = dis[v] + e[v][i].z;q.push(node(dis[e[v][i].y], e[v][i].y));}}t = min(dis[pa1], dis[pa2]);memset(dis, 0x3f3f3f3f, sizeof(dis));memset(vis, 0, sizeof(vis));dis[pa1] = 0;q.push(node(0, pa1));while(!q.empty()){v = q.top().v;q.pop();if(vis[v]) continue;vis[v] = 1;for(int i = 0; i < e[v].size(); i++)if(dis[v] + e[v][i].z < dis[e[v][i].y]){dis[e[v][i].y] = dis[v] + e[v][i].z;q.push(node(dis[e[v][i].y], e[v][i].y));}}cout<<t + dis[pa2];return 0;
}

转载于:.html