题解 P3106 【[USACO14OPEN]GPS的决斗Dueling GPS's】

· · 题解

2018.11.18 才发现venus大佬的评论，修改一个小错误 2018.10.2 修改部分解释，添加代码注释

貌似没有人用Dijkstra写呢。

其实这一题可以用Dij写的。思路其实很简单

我们可以写一个标准的dij模板，然后一共跑3遍。

分别是分3次重新构建图：

1.我们将GPS1的图存入邻接表。跑一遍dij

2.然后我们将GPS2的图再存入邻接表。再跑一遍dij

3.最后我们将2次跑过的dij,得到的最短路后所发出的警告数(分别不在2个Gps的次数)上当成边权。再跑一遍dij。

简单来说是3*汇点->源点某大佬指教的说法

每次要用不同的数组存。

最后输出dis3[1]最小警告数即可

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
#define N 10005
#define M 50005
using namespace std;
void fastin(int &a){
    char c=getchar();
    a=0;
    while((c<'0'||c>'9')&&c!='-'){  c=getchar();}
    int f=1;
    if(c=='-'){f=-1;c=getchar();}
    while(c>='0'&&c<='9'){  a=(a<<1)+(a<<3)+c-48;c=getchar();}
    a*=f;
}
int n,m;
int cnt=0;
struct Node
{
    int from,to,VA1,VA2;
}E[M];
struct Rey
{
    int nxt,to,VA;
}e[M];
int ds1[N];
int ds2[N];
int ds3[N];
struct pq
{
    int to,VA;
    bool operator < (const pq &x)const{
        return VA>x.VA;//re define 
    }//dij需要使用堆，优先队列重定向。
};
int head[N];
int vis[N];
priority_queue<pq>q;
void ADDside(int u,int v,int w)
{
    ++cnt;
    e[cnt].nxt=head[u];
    e[cnt].VA=w;
    e[cnt].to=v;
    head[u]=cnt;
}
void Dijkstra(int u,int *ds)
{
    pq now;
    for(int i=1;i<=n;i++)
    {
        ds[i]=1<<30;
        vis[i]=0;//初始化
    }
    now.to=u;
    now.VA=ds[u]=0;
    q.push(now);
    while(!q.empty())
    {
        u=q.top().to;
        q.pop();
        if(vis[u])continue;//访问过了跳过
        vis[u]=1;
        for(register int i=head[u];i!=0;i=e[i].nxt)
        {
            int v=e[i].to;
            int xl=ds[u]+e[i].VA;
            if(vis[v]==0&&xl<ds[v])
            {
                ds[v]=xl;
                now.to=v;
                now.VA=ds[v];
                q.push(now);//更新
            }
        }
    }
}//标准dij
int main()
{
    //freopen("gpsduel.in","r",stdin);
    //freopen("gpsduel.out","w",stdout);
    fastin(n);
    fastin(m);
    for(register int i=1;i<=m;i++)
    {
        fastin(E[i].to);
        fastin(E[i].from);
        fastin(E[i].VA1);
        fastin(E[i].VA2);
    }
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    cnt=0;//每次都要先初始化edge，head数组，cnt也要清理，因为要重存图
    for(register int i=1;i<=m;i++)
    {
        ADDside(E[i].from,E[i].to,E[i].VA1);//存图
    }
    Dijkstra(n,ds1);
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    cnt=0;
    for(register int i=1;i<=m;i++)
    {
        ADDside(E[i].from,E[i].to,E[i].VA2);//1次重构
    }
    Dijkstra(n,ds2);
    memset(head,0,sizeof(head));
    memset(e,0,sizeof(e));
    cnt=0;
    for(register int i=1;i<=m;i++)
    {
        int sum=0;
        if(ds1[E[i].to]!=ds1[E[i].from]+E[i].VA1)
        sum++;
        if(ds2[E[i].to]!=ds2[E[i].from]+E[i].VA2)
        sum++;
        ADDside(E[i].from,E[i].to,sum); //2次重存
    }
    Dijkstra(n,ds3);
    printf("%d",ds3[1]);//最少的警告数
    putchar('\n');
    return 0;
}