选拔赛-最短路

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

裸的最短路？？

-_-||

 

第一种方法：

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

抄的牛的代码，spfa。。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=10010;
const int maxe=20010;
const int inf=0x3f3f3f3f;

int n,m,ss,ee;
int t;

int dis[maxn][2];  //双状态
int inq[maxn][2];

struct edge
{
    int v,nex;
    int a,b;
}e[maxe*2];

int head[maxn];
int cnt;
void add(int u,int v,int a,int b)
{
    e[cnt].v=v;
    e[cnt].a=a;
    e[cnt].b=b;
    e[cnt].nex=head[u];
    head[u]=cnt++;
}

void spfa()
{
    queue<int>q;
    q.push(ss);
    q.push(0);
    dis[ss][0]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        int mask=q.front();
        q.pop();
        inq[u][mask]=0;
        for(int i=head[u];i!=-1;i=e[i].nex)
        {
            int v=e[i].v;
            int a=e[i].a;
            int b=e[i].b;
            int cc=mask?b:a;
            int mask2=(cc&1)^mask;   // 位运算很巧妙！！
            if(dis[v][mask2]>dis[u][mask]+cc)
            {
                dis[v][mask2]=dis[u][mask]+cc;
                if(!inq[v][mask2])
                {
                    inq[v][mask2]=1;
                    q.push(v);
                    q.push(mask2);
                }
            }
        }
    }
}

int main()
{
    int T;
    int u,v,a,b;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d%d",&n,&m,&ss,&ee);
        for(int i=0;i<=n;i++) head[i]=-1;
        cnt=0;
        memset(inq,0,sizeof(inq));
        memset(dis,0x3f3f3f,sizeof dis);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&u,&v,&a,&b);
            add(u,v,a,b);
            add(v,u,a,b);
        }
        spfa();
        int ans=min(dis[ee][0],dis[ee][1]);
        if(ans==inf) puts("-1");
        else printf("%d\n",ans);
    }
}

 

第二种方法：

拆点。。

对每个点 x拆成两个点 2x,2x+1  分别表示绿灯状态和红灯状态。
对于绿灯奇数时间的路线 a,b 连接  2a→2b+1 和 2b→2a+1，其他路线类似。
最后跑一遍标准的 SPFA 即可

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

#include<bits/stdc++.h>
#define IN(x) (x<<1)
#define OUT(x) (x<<1|1)
using namespace std;

const int maxn=10000*2+10;
const int INF=~0U>>2;

struct edge{int from,to,dis;};

struct SPFA{
    int n;
    vector<int>G[maxn];
    vector<edge>E;
    int d[maxn];
    bool vis[maxn];
    
    void init(int n){
        this->n=n;
        for(int i=0;i<=n;i++)G[i].clear();
        E.clear();
    }

    void addedge(int from,int to,int dis){
        E.push_back((edge){from,to,dis});
        G[from].push_back(E.size()-1);
    }

    void exec(int S){
        for(int i=0;i<=n;i++)d[i]=INF,vis[i]=0;
        d[S]=0,vis[S]=1;
        queue<int>Q;
        Q.push(S);
        while(!Q.empty()){
            int x=Q.front();
            Q.pop();vis[x]=0;
            for(int i:G[x]){
                edge &e=E[i];
                if(d[e.to]>d[e.from]+e.dis){
                    d[e.to]=d[e.from]+e.dis;
                    if(!vis[e.to]){
                        vis[e.to]=1;
                        Q.push(e.to);
                    }
                }
            }
        }
    }

    int value(int x){return d[x];}
}app;



int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int n,m,s,t;
        scanf("%d%d%d%d",&n,&m,&s,&t);
        s--,t--;
        app.init(n*2);
        for(int i=1;i<=m;i++){
            int a,b,c,d;
            scanf("%d%d%d%d",&a,&b,&c,&d);
            a--,b--;
            app.addedge(IN(a),IN(b)^(c&1),c);
            app.addedge(IN(b),IN(a)^(c&1),c);
            app.addedge(OUT(a),OUT(b)^(d&1),d);
            app.addedge(OUT(b),OUT(a)^(d&1),d);
        }    
        app.exec(IN(s));
        printf("%d\n",min(app.value(IN(t)),app.value(OUT(t))));
    }
    return 0;
}