一个基于优先队列的做法

课上老师讲了一个 O( {n}^{4} ) 的算法，表示没有听懂，就自己瞎搞，最后整出了如这篇题解的思路。

题目给的约束条件是:

1. 两人同时到达。
2. 时间最短。

先着手考虑第二个约束条件，时间最短，那就尽可能地贪。不难联想到求两人 1\to n 的最短路。 如果这道题只是求两人分别从 1\to n 的最短路（单点 \to 单点），那么就可以用两个优先队列。

这里以其中一个人为例：

我们把她起始点连的所有点带上到达所需时间（边权）一起 rua 进优先队列里去，每次再拿出来优先队列里权值最小的点，再将所有的子节点带上边权再 rua 进去，直到拿出的点为 n 号节点（目标节点）为止。而第一次取出 n 号节点必定就是从 1\to n 的最短路。

先贴代码：

struct u2004{
    int p,t;//p为节点编号,t为从 1->n 路径权
    bool operator < (const u2004 x)const{
        if(x.t==t)return p<x.p;
        return t>x.t;
    }
};
inline void pre(){
    for(int i=head[1];i;i=e[i].nx)
        q.push((u2004){e[i].b,e[i].va});
}
inline int get(){
    while(!q.empty()){
        u2004 x=q.top();
        q.pop();
        if(x.p==n)return x.t;
        int t=x.t;
        for(int i=head[x.p];i;i=e[i].nx){
            int y=e[i].b;
            q.push((u2004){e[i].b,t+e[i].va1});
        }
    }
    return 0;
}

简单解释一下，设从优先队列里取出的节点是 u ，则第一次取 u时 必定优先队列里 1\to u 最短的路径。

用反证法证明一下：若第一次取出的不为 1\to u 的最短路，则必有节点 v，使得 {S}_{1\to v}+{S}_{v\to u}< {S}_{1\to u}

因为路径消耗时间为正数，则必有 {S}_{1\to v}<{S}_{1\to u}

则理应优先取出来 1\to v 的路径，并进行更新。而现在取出的路径为 1\to u ,矛盾，故得证。

但是，由于约束条件一，而每条路两人所用时间不一定相同，致使两个人的最短路不一定相同，即不一定是最终解。

时间 41ms,吸一口氧气后时间 37ms。

代码：

#include<cstdio>
#include<queue>
#define N 105
using namespace std;
int n,m,last;
int head[N];
struct u2003{
    int nx,b,va1,va2;//va1,va2分别是两个人通过路径的用时
}e[N*N/2];
inline void build(int a,int b,int va1,int va2){
    e[++last].b=b;
    e[last].va1=va1;
    e[last].va2=va2;
    e[last].nx=head[a];
    head[a]=last;
}
inline void scan(){
    scanf("%d%d",&n,&m);
    int a,b,c,d;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        build(a,b,c,d);
    }
}
struct u2004{
    int p,t;
    bool operator < (const u2004 x)const{
        if(x.t==t)return p<x.p;
        return t>x.t;//可能没啥用
    }
};
priority_queue<u2004> q1,q2;
inline void pre(){
    for(int i=head[1];i;i=e[i].nx){
        q1.push((u2004){e[i].b,e[i].va1});
        q2.push((u2004){e[i].b,e[i].va2});
    }
}
inline int get1(){
    while(!q1.empty()){
        u2004 x=q1.top();
        q1.pop();
        if(x.p==n)return x.t;
        int t=x.t;
        for(int i=head[x.p];i;i=e[i].nx){
            int y=e[i].b;
            q1.push((u2004){e[i].b,t+e[i].va1});
        }
    }
    return 0;
}
inline int get2(){
    while(!q2.empty()){
        u2004 x=q2.top();   
        q2.pop();
        if(x.p==n)return x.t;
        int t=x.t;
        for(int i=head[x.p];i;i=e[i].nx){
            int y=e[i].b;
            q2.push((u2004){e[i].b,t+e[i].va2});
        }
    }
    return 0;
}
inline int suan(){
    int x1=get1();
    int x2=get2();
    while(x1!=x2){//不相等时对较小的1->n路径更新次短路
        if(x1<x2)x1=get1();
        else x2=get2();
        if(!x1||!x2)return 0;//为0即1->n所有路径与对方无重合
    }
    return x1;//x2也行
}
int main(){
    scan();
    pre();
    int x=suan();
    if(x==0)puts("IMPOSSIBLE");
    else printf("%d\n",x);
    return 0;
}

憨憨第一次写题解，感谢管理员大大的指点~~ 耽误了管理好多时间