German Collegiate Programming Contest 2015 计蒜课

 
// 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
");
73              return  0;
74              }
75              else{
76                  printf("yes
");
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
");
74              return  0;
75              }
76              else{
77                  printf("yes
");
78              }
79              return 0;
80 }