题目描述

这天,$tokitsukaze$带着她的舰队去才归一儿海探索。

这个海域有$n$个站点,深海舰队控制着这片海域的$m$条航。

这些航线连接着这$n$个点,第$i$条航线连接着$u_i$,$v_i$两个点。

航线都是正确的,也就是说没有重复的航线,也没有任何一个点与自己相连。

$tokitsukaze$的舰队经过第$i$条航线时,会受到来自深海舰队的$ai$点伤害。

$tokitsukaze$可以在某个休息站点将接下来的战斗切换至夜战模式,这样在她的舰队经过第$i$条航线时,受到的伤害就变为

$b_i$,不过一旦切换到夜战模式就不能再次切换回来,所以她必须考虑清楚在哪里切换。

现在有个限时活动。活动难度分为$1,2,3,4,...n$。

在难度$1$下,$tokitsukaze$可以在任意站点切换到夜战模式。

而在难度$2$下,不能在站点$1$切换到夜战模式。

在难度$3$下,不能在站点$1,2$切换模式...

以此类推,即在难度$k$下,$tokitsukaze$不能在站点$1,2,3,4,5...k-1$切换模式。

同时,活动还要求在游戏结束时必须处于夜战模式。

现在$tokitsukaze$的舰队从$s$点出发,要前往深海大本营所在的$t$点。

请你告诉她,在难度为$1,2,3,4,5...n$时,她的舰队结束游戏时受到的最小伤害。

输入描述

第一行包括$2$个正整数$n,m$($2≤n≤10^5$,$1≤m≤min(\frac{n \times(n-1)}{2},10^5)$)。
接下来$m$行,每行包括$4$个正整数$u,v,a,b$($1≤u,v≤n$,$1≤a,b≤10^9$)。
最后一行包括$2$个正整数$s,t$($1≤s,t≤n$)。

输出描述:

共$n$行,每行一个整数,表示在难度为$1,2..n$时,结束游戏时舰队受到的最小伤害。

样例输入

4 3
1 4 1 30
1 2 1 10
1 3 20 1
2 3

样例输出

2
11
21
33

样例说明

活动难度为$1$时,在编号为$1$的点切换模式,受到的最小伤害为$2$。
活动难度为$2$时,在编号为$2$的点切换模式,受到的最小伤害为$11$。
活动难度为$3$时,在编号为$3$的点切换模式,受到的最小伤害为$21$。
活动难度为$4$时,在编号为$4$的点切换模式,受到的最小伤害为$33$。

菜鸡的咆哮

可以将两个模式抽象成两张结构相同权值不同的无向无环图。

求从图$1$的$s$出发到图$2$的$t$的最短路(可以在某个时刻从图$1$跳到图$2$)。

刚开始建了一个两层的图,对$1-n$上下连边。

$n$遍最短路死的很安详$QAQ$。

看了题解 经过思考后发现:

如果我们定义$dist_1[x]$表示在图$1$中$s$到$x$的最短路;

​ $dist_2[x]$表示在图$2$中$x$到$t$的最短路。

那么在点$x$转移状态的最小代价为$dist_1[x]+dist_2[x]$。

又因为在难度$k$下能够转移的点在难度$k-1$下也一定能被转移。

所以从后向前枚举$x$取最小值就可以了。

代码

#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
inline int read(){
    char ch=getchar();int s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-48;ch=getchar();}
    return s*w;
}
int n,m;
struct data{
    int to;
    int p[3];
    int nextt;
}line[2*maxn];
int first[maxn];
int tail;
void add(int x,int y,int w1,int w2){
    tail++;
    line[tail].to=y;
    line[tail].p[1]=w1;
    line[tail].p[2]=w2;
    line[tail].nextt=first[x];
    first[x]=tail;
}
queue<int> q;
ll dist[3][maxn];
int inqueue[maxn];
void spfa(int s,int pos){
    dist[pos][s]=0;
    q.push(s);inqueue[s]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        inqueue[x]=0;
        for(int i=first[x];i;i=line[i].nextt){
            int y=line[i].to;
            int w=line[i].p[pos];
            if(dist[pos][y]>dist[pos][x]+w){
                dist[pos][y]=dist[pos][x]+w;
                if(inqueue[y]==0){
                    q.push(y);
                    inqueue[y]=1;
                }
            }
        }
    }
}
int s,t;
ll ans[maxn];
int main(){
    n=read();m=read();
    int x,y,w1,w2;
    for(int i=1;i<=m;i++){
        x=read();y=read();
        w1=read();w2=read();
        add(x,y,w1,w2);
        add(y,x,w1,w2);
    }
    s=read();t=read();
    memset(dist,0x3f,sizeof(dist));
    spfa(s,1);
    spfa(t,2);
    memset(ans,0x3f,sizeof(ans));
    for(int i=n;i>=1;i--){
        ans[i]=min(ans[i+1],dist[1][i]+dist[2][i]);
    }
    for(int i=1;i<=n;i++){
        printf("%lld\n",ans[i]);
    }
    return 0;
}