Flowery Trails
!”
()”
*+,-).%”
/)’0”
122”
1!2”
342”
522”
!22”
652”
!42”
72” 72”
5!2”
!12” 622”
18!” 162”
!12”
6”
7”
4”
9”
3”
5”
8”
1”
2”
In order to attract more visitors, the manager of
a national park had the idea of planting flowers
along both sides of the popular trails, which are
the trails used by common people. Common people
only go from the park entrance to its highest peak,
where views are breathtaking, by a shortest path.
So, he wants to know how many metres of flowers
are needed to materialize his idea.
For instance, in the park whose map is depicted
in the figure, common people make only one of the
three following paths (which are the shortest paths
from the entrance to the highest peak).
• At the entrance, some start in the rightmost
trail to reach the point of interest 3 (after
100 metres), follow directly to point 7 (200
metres) and then pick the direct trail to the
highest peak (620 metres).
• The others go to the left at the entrance and
reach point 1 (after 580 metres). Then, they take one of the two trails that lead to
point 4 (both have 90 metres). At point 4, they follow the direct trail to the highest
peak (250 metres).
Notice that popular trails (i.e., the trails followed by common people) are highlighted in
yellow. Since the sum of their lengths is 1930 metres, the extent of flowers needed to cover
both sides of the popular trails is 3860 metres (3860 = 2 × 1930).
Task
Given a description of the park, with its points of interest and (two-way) trails, the goal
is to find out the extent of flowers needed to cover both sides of the popular trails. It is
guaranteed that, for the given inputs, there is some path from the park entrance to the
highest peak.
Input
The first line of the input has two integers: P and T. P is the number of points of interest
and T is the number of trails. Points are identified by integers, ranging from 0 to P − 1.
The entrance point is 0 and the highest peak is point P − 1.
Universidade do Porto Computer Science Department 5
Problem B Problem B
Each of the following T lines characterises a different trail. It contains three integers,
p1, p2, and l, which indicate that the (two-way) trail links directly points p1 and p2 (not
necessarily distinct) and has length l (in metres).
Integers in the same line are separated by a single space.
Constraints
2 ≤ P ≤ 10 000 Number of points.
1 ≤ T ≤ 250 000 Number of trails.
1 ≤ l ≤ 1 000 Length of a trail.
Output
The output has a single line with the extent of flowers (in metres) needed to cover both
sides of the popular trails.
Sample Input 1
10 15
0 1 580
1 4 90
1 4 90
4 9 250
4 2 510
2 7 600
7 3 200
3 3 380
3 0 150
0 3 100
7 8 500
7 9 620
9 6 510
6 5 145
5 9 160
Sample Output 1
3860
Sample Input 2
4 7
0 1 1
0 2 2
0 3 10
0 3 3
1 3 2
2 3 1
1 1 1
Sample Output 2
18
思路：先从s->t 跑一遍spfa,再从 t->s 跑一遍，分别求出距离长度；
接着：易知 如果某一点 m，s->m 的最短距离+m->m.to的距离+m.to->t==最短路长度，那么这一段就在最短路上面。
#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
#define inf 0x3f3f3f3f
typedef long long ll;
struct edge
{
int to,w,next;
}e[maxn];
int head[maxn],vis[maxn];
int d1[maxn],d2[maxn];
int n,m ,t;
//ll ans;
void add(int i,int j,int w)
{
// e[t].from=i;
e[t].to=j;
e[t].w=w;
e[t].next=head[i];
head[i]=t++;
}
void spfa(int s,int t ,int d[])
{
queue<int> q;
for(int i=0;i<n;i++){
d[i]=inf;
}
memset(vis,false,sizeof(vis));
q.push(s);
d[s]=0;
vis[s]=true;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(d[v]>d[u]+e[i].w){
d[v]=d[u]+e[i].w;
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
}
void sol()
{
int s=0,t=n-1;
ll ans=0;
spfa(s,t,d1);
spfa(t,s,d2);
ll minn=d1[t];
for(int u=0;u<n;u++){
for(int i=head[u];~i;i=e[i].next){
ll v=e[i].to;
ll weight=e[i].w;
if(d1[u]+d2[v]+weight==minn){
ans+=weight;
}
}
}
cout<<ans*2<<endl;
}
int main()
{
//int n,m;
while(cin>>n>>m){
memset(head,-1,sizeof(head));
t=0;
for(int i=0;i<m;i++){
int u,v,l;
cin>>u>>v>>l;
add(u,v,l);
add(v,u,l);
}
sol();
}
}