bzoj2100 [Usaco2010 DEC]Apple Delivery苹果贸易

题目描述

一张P个点的无向图，C条正权路。CLJ要从Pb点（家）出发，既要去Pa1点NOI赛场拿金牌，也要去Pa2点CMO赛场拿金牌。（途中不必回家）可以先去NOI，也可以先去CMO。当然神犇CLJ肯定会使总路程最小，输出最小值。

题解：做两遍spfa，找出从起点开始先去pa1或者先去pa2的最小值

需要用一下spfa的优化，每次进行入队的时候都与队头进行比较，如果比队头小就放在队头，否则放队尾。

#include<bits/stdc++.h>

using namespace std;

#define maxn 100005

#define maxm 200005

int dis[maxn],head[maxn],q[maxn];

bool vis[maxn];

struct edge{

    int next,to,w;

}e[maxm*];

int n,m,s,t1,t2;

int ans=,cnt;

inline int read(){

    int x=,f=;char ch=getchar();

    while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

void insert(int u,int v,int w){

    cnt++;

    e[cnt].next=head[u];e[cnt].to=v;e[cnt].w=w;

    head[u]=cnt;

}

void spfa(int x){

    memset(dis,,sizeof dis);

    vis[x]=;dis[x]=;q[]=x;

    int top=,tail=;

    while(top!=tail)

    {

        int now=q[top];top++;

        if(top==)top=;

        for(int i=head[now];i;i=e[i].next){

            int p=e[i].to;

            if(dis[p]>dis[now]+e[i].w){

                dis[p]=dis[now]+e[i].w;

                if(!vis[p]){

                    vis[p]=;

                    if(dis[p]<dis[q[top]]){

                        top--;if(top<)top=;

                        q[top]=p;

                    }

                    else{

                        q[tail++]=p;

                        if(tail==)tail=;

                    }

                }

            }

        }

        vis[now]=;

    }

}

int main(){

    m=read();n=read();s=read();t1=read();t2=read();

    int u,v,w;

    for(int i=;i<=m;i++){

        u=read();v=read();w=read();

        insert(u,v,w);insert(v,u,w);

    }

    spfa(t1);

    ans=dis[s]+dis[t2];

    spfa(t2);

    ans=min(ans,dis[s]+dis[t1]);

    printf("%d",ans);

}