选拔赛-最短路

还是太菜了吧，，这都不会

裸的最短路？？

-_-||

第一种方法：

每个点有记录两个状态，红灯和绿灯分开记

抄的牛的代码，spfa。。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=10010;
 7 const int maxe=20010;
 8 const int inf=0x3f3f3f3f;
 9 
10 int n,m,ss,ee;
11 int t;
12 
13 int dis[maxn][2];  //双状态
14 int inq[maxn][2];
15 
16 struct edge
17 {
18     int v,nex;
19     int a,b;
20 }e[maxe*2];
21 
22 int head[maxn];
23 int cnt;
24 void add(int u,int v,int a,int b)
25 {
26     e[cnt].v=v;
27     e[cnt].a=a;
28     e[cnt].b=b;
29     e[cnt].nex=head[u];
30     head[u]=cnt++;
31 }
32 
33 void spfa()
34 {
35     queue<int>q;
36     q.push(ss);
37     q.push(0);
38     dis[ss][0]=0;
39     while(!q.empty())
40     {
41         int u=q.front();
42         q.pop();
43         int mask=q.front();
44         q.pop();
45         inq[u][mask]=0;
46         for(int i=head[u];i!=-1;i=e[i].nex)
47         {
48             int v=e[i].v;
49             int a=e[i].a;
50             int b=e[i].b;
51             int cc=mask?b:a;
52             int mask2=(cc&1)^mask;   // 位运算很巧妙！！
53             if(dis[v][mask2]>dis[u][mask]+cc)
54             {
55                 dis[v][mask2]=dis[u][mask]+cc;
56                 if(!inq[v][mask2])
57                 {
58                     inq[v][mask2]=1;
59                     q.push(v);
60                     q.push(mask2);
61                 }
62             }
63         }
64     }
65 }
66 
67 int main()
68 {
69     int T;
70     int u,v,a,b;
71     scanf("%d",&T);
72     while(T--)
73     {
74         scanf("%d%d%d%d",&n,&m,&ss,&ee);
75         for(int i=0;i<=n;i++) head[i]=-1;
76         cnt=0;
77         memset(inq,0,sizeof(inq));
78         memset(dis,0x3f3f3f,sizeof dis);
79         for(int i=0;i<m;i++)
80         {
81             scanf("%d%d%d%d",&u,&v,&a,&b);
82             add(u,v,a,b);
83             add(v,u,a,b);
84         }
85         spfa();
86         int ans=min(dis[ee][0],dis[ee][1]);
87         if(ans==inf) puts("-1");
88         else printf("%d
",ans);
89     }
90 }

第二种方法：

拆点。。

对每个点

今天好累，不想打了，先直接贴上吧。。

 1 #include<bits/stdc++.h>
 2 #define IN(x) (x<<1)
 3 #define OUT(x) (x<<1|1)
 4 using namespace std;
 5 
 6 const int maxn=10000*2+10;
 7 const int INF=~0U>>2;
 8 
 9 struct edge{int from,to,dis;};
10 
11 struct SPFA{
12     int n;
13     vector<int>G[maxn];
14     vector<edge>E;
15     int d[maxn];
16     bool vis[maxn];
17     
18     void init(int n){
19         this->n=n;
20         for(int i=0;i<=n;i++)G[i].clear();
21         E.clear();
22     }
23 
24     void addedge(int from,int to,int dis){
25         E.push_back((edge){from,to,dis});
26         G[from].push_back(E.size()-1);
27     }
28 
29     void exec(int S){
30         for(int i=0;i<=n;i++)d[i]=INF,vis[i]=0;
31         d[S]=0,vis[S]=1;
32         queue<int>Q;
33         Q.push(S);
34         while(!Q.empty()){
35             int x=Q.front();
36             Q.pop();vis[x]=0;
37             for(int i:G[x]){
38                 edge &e=E[i];
39                 if(d[e.to]>d[e.from]+e.dis){
40                     d[e.to]=d[e.from]+e.dis;
41                     if(!vis[e.to]){
42                         vis[e.to]=1;
43                         Q.push(e.to);
44                     }
45                 }
46             }
47         }
48     }
49 
50     int value(int x){return d[x];}
51 }app;
52 
53 
54 
55 int main(){
56     int T;
57     scanf("%d",&T);
58     while(T--){
59         int n,m,s,t;
60         scanf("%d%d%d%d",&n,&m,&s,&t);
61         s--,t--;
62         app.init(n*2);
63         for(int i=1;i<=m;i++){
64             int a,b,c,d;
65             scanf("%d%d%d%d",&a,&b,&c,&d);
66             a--,b--;
67             app.addedge(IN(a),IN(b)^(c&1),c);
68             app.addedge(IN(b),IN(a)^(c&1),c);
69             app.addedge(OUT(a),OUT(b)^(d&1),d);
70             app.addedge(OUT(b),OUT(a)^(d&1),d);
71         }    
72         app.exec(IN(s));
73         printf("%d
",min(app.value(IN(t)),app.value(OUT(t))));
74     }
75     return 0;
76 }