题目描述
贝西有两个又香又脆的红苹果要送给她的两个朋友。当然她可以走的C（1<=C<=200000）条“牛路”都被包含在一种常用的图中，包含了P（1<=P<=100000）个牧场，分别被标为1..P。没有“牛路”会从一个牧场又走回它自己。“牛路”是双向的，每条牛路都会被标上一个距离。最重要的是，每个牧场都可以通向另一个牧场。每条牛路都连接着两个不同的牧场P1_i和P2_i（1<=P1_i,p2_i<=P)，距离为D_i。所有“牛路”的距离之和不大于2000000000。
现在，贝西要从牧场PB开始给PA_1和PA_2牧场各送一个苹果（PA_1和PA_2顺序可以调换），那么最短的距离是多少呢？当然，PB、PA_1和PA_2各不相同。
输入格式
Line 1: Line 1 contains five space-separated integers: C, P, PB, PA1, and PA2
Lines 2..C+1: Line i+1 describes cowpath i by naming two pastures it connects and the distance between them: P1_i, P2_i, D_i
输出格式
Line 1: The shortest distance Bessie must travel to deliver both apples
输入样例
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
Solution
这道题可用最短路解决，要么从1跑到p1再跑到p2，要么从1跑到p2再跑到p1，所以我们可以跑两遍dijkstra解决。
因为SPFA在今年的NOI那啥了，所以只要没有负边权我就坚持不用SPFA。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define SIZE 1000100
using namespace std;
int head[SIZE],n,m,s,ecnt,dis[SIZE];
bool vis[SIZE];
int min(int a,int b){
return a<b?a:b;
}
struct node {
int id,w;
};
struct edge {
int v,nxt,dist;
} e[4*SIZE];
bool operator <(node a,node b) {
return (a.w>b.w);
}
void add_edge(int from,int to,int dis) {
e[++ecnt]=(edge) {
to,head[from],dis
};
head[from]=ecnt;
}
void dijkstra(int u) {
memset(dis,0x7f,sizeof(dis));
memset(vis,0,sizeof(vis));
priority_queue<node>q;
dis[u]=0;
q.push((node) {u,0});
while(!q.empty()) {
node flag=q.top();
q.pop();
int v=flag.id;
if(vis[v]) continue;
vis[v]=1;
for(int i=head[v]; i; i=e[i].nxt) {
int to=e[i].v;
if(dis[to]>dis[v]+e[i].dist) {
dis[to]=dis[v]+e[i].dist;
q.push((node){to,dis[to]});
}
}
}
}
int main() {
int p1,p2;
scanf("%d%d%d%d%d",&m,&n,&s,&p1,&p2);
int x,y,z;
for(int i=1; i<=m; i++) {
scanf("%d%d%d",&x,&y,&z);
add_edge(x,y,z);
add_edge(y,x,z);
}
dijkstra(p1);
int ans1=dis[s]+dis[p2];
dijkstra(p2);
int ans2=dis[s]+dis[p1];
printf("%d",min(ans2,ans1));
return 0;
}
|
