P3116
渔歌
2021-08-21 15:59:05
# 一个基于优先队列的做法
课上老师讲了一个 $ O( {n}^{4} ) $ 的算法，表示没有听懂，就自己~~瞎搞~~，最后整出了如这篇题解的思路。
题目给的约束条件是:
1. 两人同时到达。
2. 时间最短。
先着手考虑第二个约束条件，时间最短，那就尽可能地贪。不难联想到求两人 **$1\to n$ 的最短路**。
如果这道题只是求两人分别从 $1\to n$ 的最短路（单点 $ \to$ 单点），那么就可以用两个**优先队列**。
这里以其中一个人为例：
我们把她起始点连的所有点带上到达所需时间（边权）一起 rua 进优先队列里去，每次再拿出来优先队列里权值最小的点，再将所有的子节点带上边权再 rua 进去，直到拿出的点为 $n$ 号节点（目标节点）为止。而第一次取出 $n$ 号节点必定就是从 $1\to n$ 的最短路。
先贴代码：
```cpp
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$ ,矛盾，故得证。
但是，由于约束条件一，而每条路两人所用时间不一定相同，致使两个人的最短路不一定相同，即不一定是最终解。
$But$ 我们可以利用最短路的思路。在求 $1\to n$ 最短路过程中，我们每次进行更新的结果不一定是最优解，但我们还是会老老实实rua进优先队列，那么优先队列里必定存有 $1\to n$ 的第 2 短路，第 3 短路·····第 k 短路，甚至最长路。当 $1\to u$ 的最短路被取出时，剩下的便是第二短路等**次优解**。而通过之前的证明同理可得（懒得证明），**第k次取出的 $1\to u$ 便是 $1\to u$ 的第 k 短路**。(此处为不严格第 k 短路，可能与 k-1 短路相等。)
但我们没有必要老老实实把两个人的所有路径都存起来。因为我们找到的第 k 短路是不下降的， 则我们可以动态更新，每次将耗时较少的(路径长度较短的）进行更新，再进行比较，直至相同，或 $1\to n$ 路径均被取出。
$Over$
时间 41ms,吸一口氧气后时间 37ms。
代码：
```cpp
#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;
}
```
憨憨第一次写题解，感谢管理员大大的指点~~
~~耽误了管理好多时间~~