SlowLeak

You are an avid cyclist and bike every day between your home and school. Usually, your ride is uneventful and you bike along the shortest path between home and school. After school this afternoon you realized you have a slow leak in your bike tire——the tire can hold some air, but not for long. Refilling the tire allows you to ride your bike for some distance, after which your tire goes flat again and it becomes impossible to ride any further (and you refuse to walk your bicycle).

Luckily for you, your city has installed several bike repair stations at intersections throughout town where you can refill your tire and bike again until the tire goes flat. There's a repair station at your school too, so that you can fill up your tire before you start on your trip home.

You've calculated how far you can bike before your tire runs out of air and you know the layout of your town, including all the intersections, distances between them, and the locations of the repair stations. What is the shortest possible trip from school to your home that you can take without becoming stuck due to a flat tire? (You do not become stuck if you roll into a repair station, or your home, at the exact same time as your tire goes flat.)

The first line of input contains four integers $n$ , $m$ , $t$ , and $d$ , satisfying $2 \leq n \leq 500$ , $0 < m \leq n*(n - 1)/2$ , $0 < t < n$ and $0 < d < 2^{31}$ . The value $n$ represents the number of intersections in the city, $m$ represents the number of roads in the city, $t$ is the number of repair stations and $d$ is the distance that you can bike (starting with a fully inflated tire) before your tire goes flat again. The intersections are numbered from $1$ to $n$ . Your school is at intersection $1$ and your home is at intersection $n$ .

The second line of input contains $t$ integers, with values between $2$ and $n − 1$ , inclusive. These are the intersections where the repair stations are located (excluding your school's repair station). All integers on this line are unique.

The next $m$ lines represent the roads in your town. Each has three integers $i, j, k$ , where $1 \leq i < j \leq n$ , and $0 < k < 2^{31}$ . These three integers represent that there is a direct road from intersection $i$ to intersection $j$ of length $k$ . Roads can be traveled in either direction. There is at most one road between any two intersections.

Print the minimum total distance you need to travel to reach home from school without getting stuck due to a flat tire. If the trip is not possible, output the word stuck on a single line instead.

It is guaranteed that if the trip is possible, the minimum distance $D$ satisfies $0 < D < 2^{31}$ .

#include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(ll i=1;i<=n;i++) const int N=1e5+7; const ll inf=0x3f3f3f3f3f; ll n,m,t,d; int a[555]; ll g[555][555]; int main() { cin>>n>>m>>t>>d; rep(i,t) cin>>a[i]; a[++t]=1,a[++t]=n; memset(g,inf,sizeof(g)); rep(i,m) { int x,y; ll z; cin>>x>>y>>z; g[x][y]=g[y][x]=z; } rep(k,n) rep(i,n) rep(j,n) g[i][j]=min(g[i][j],g[i][k]+g[k][j]); rep(i,t) rep(j,t) { int x=a[i],y=a[j]; if(g[x][y]>d) g[x][y]=inf; } rep(x,t) rep(y,t) rep(z,t) { int k=a[x],i=a[y],j=a[z]; g[i][j]=min(g[i][j],g[i][k]+g[k][j]); } if(g[1][n]==inf) cout<<"stuck"<<endl; else cout<<g[1][n]<<endl; return 0; }

详情