// Change of Scenery
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <cstring>
5 #include <vector>
6 #include <utility>
7 #include <queue>
8 using namespace std;
9 typedef long long ll;
10 typedef pair<int,int>P;
11 int n,m,k;
12 const int N=10010;
13 const ll inf=1e10+9;
14 const ll mod=1e9+7;
15 struct Node{
16 int to;
17 ll w;
18 Node(){}
19 Node(int TO,ll W){
20 to=TO;
21 w=W;
22 }
23 };
24 vector<Node>vec[N];
25 int prenum[N];
26 ll dis[N];
27 void bfs(int sta){
28 priority_queue<P,vector<P>,greater<P> >que;
29 dis[sta]=0;
30 prenum[sta]=1;
31 que.push(P(0,sta));
32 while(!que.empty())
33 {
34 P q=que.top();
35 que.pop();
36 int v=q.second;
37 if(dis[v]<q.first) continue;
38 for(int i=0;i<vec[v].size();i++){
39 Node Nod=vec[v][i];
40 int t=Nod.to;
41 if(dis[t]>dis[v]+Nod.w){
42 dis[t]=dis[v]+Nod.w;
43 prenum[t]=prenum[v];
44 que.push(P(dis[t],t));
45 }
46 else if(dis[t]==dis[v]+Nod.w){
47 prenum[t]=(prenum[t]+prenum[v])%mod;//關鍵點
48 //本題的路徑數目可能很多，long long 也不一定滿足，因為路徑數目用的是
49 //乘法原理，是以要取餘
50 }
51 }
52 }
53 }
54 int main()
55 {
56 scanf("%d%d%d",&n,&m,&k);
57 int xx;
58 for(int i=0;i<k;i++){
59 scanf("%d",&xx);
60 }
61 int x,y;
62 ll z;
63 for(int i=0;i<m;i++){
64 scanf("%d%d%lld",&x,&y,&z);
65 vec[x].push_back(Node(y,z));
66 vec[y].push_back(Node(x,z));//這是個無向圖
67 }
68 for(int i=1;i<=n;i++)
69 dis[i]=inf;
70 bfs(1);
71 if(prenum[n]<2){
72 printf("no\n");
73 return 0;
74 }
75 else{
76 printf("yes\n");
77 }
78 return 0;
79 }
1 // German Collegiate Programming Contest 2015 計蒜課 Change of Scenery
2 #include <iostream>
3 #include <cstdio>
4 #include <algorithm>
5 #include <cstring>
6 #include <vector>
7 #include <utility>
8 #include <queue>
9 using namespace std;
10 typedef long long ll;
11 typedef pair<int,int>P;
12 int n,m,k;
13 const int N=10010;
14 const ll inf=1e10+9;
15 const ll mod=1e9+7;
16 struct Node{
17 int to;
18 ll w;
19 Node(){}
20 Node(int TO,ll W){
21 to=TO;
22 w=W;
23 }
24 };
25 vector<Node>vec[N];
26 int prenum[N];
27 ll dis[N];
28 void bfs(int sta){
29 priority_queue<P,vector<P>,greater<P> >que;
30 dis[sta]=0;
31 prenum[sta]=1;
32 que.push(P(0,sta));
33 while(!que.empty())
34 {
35 P q=que.top();
36 que.pop();
37 int v=q.second;
38 if(dis[v]<q.first) continue;
39 for(int i=0;i<vec[v].size();i++){
40 Node Nod=vec[v][i];
41 int t=Nod.to;
42 if(dis[t]>dis[v]+Nod.w){
43 dis[t]=dis[v]+Nod.w;
44 prenum[t]=prenum[v];
45 que.push(P(dis[t],t));
46 }
47 else if(dis[t]==dis[v]+Nod.w){
48 prenum[t]=(prenum[t]+prenum[v])%mod;//關鍵點
49 //本題的路徑數目可能很多，long long 也不一定滿足，因為路徑數目用的是
50 //乘法原理，是以要取餘
51 }
52 }
53 }
54 }
55 int main()
56 {
57 scanf("%d%d%d",&n,&m,&k);
58 int xx;
59 for(int i=0;i<k;i++){
60 scanf("%d",&xx);
61 }
62 int x,y;
63 ll z;
64 for(int i=0;i<m;i++){
65 scanf("%d%d%lld",&x,&y,&z);
66 vec[x].push_back(Node(y,z));
67 vec[y].push_back(Node(x,z));//這是個無向圖
68 }
69 for(int i=1;i<=n;i++)
70 dis[i]=inf;
71 bfs(1);
72 if(prenum[n]<2){
73 printf("no\n");
74 return 0;
75 }
76 else{
77 printf("yes\n");
78 }
79 return 0;
80 }
