【牛客练习赛50】 tokitsukaze and Event

题目描述

这天，tokitsukaze带着她的舰队去才归一儿海探索。这个海域有 $n$n个站点，深海舰队控制着这片海域的 $m$m条航线，这些航线连接着这 $n$n个点，第i条航线连接着 $u_i$ui​， $v_i$vi​两个点。航线都是正确的，也就是说没有重复的航线，也没有任何一个点与自己相连。tokitsukaze的舰队经过第i条航线时，会受到来自深海舰队的 $a_i$ai​点伤害。

tokitsukaze可以在某个休息站点将接下来的战斗切换至夜战模式，这样在她的舰队经过第i条航线时，受到的伤害就变为 $b_i$bi​，不过一旦切换到夜战模式就不能再次切换回来，所以她必须考虑清楚在哪里切换。

现在有个限时活动。活动难度分为 $1,2,3,4,...n$1,2,3,4,...n，在难度1下，tokitsukaze可以在任意站点切换到夜战模式，而在难度 $2$2下，不能在站点 $1$1切换到夜战模式，在难度 $3$3下，不能在站点 $1,2$1,2切换模式…以此类推，即在难度 $k$k下，tokitsukaze不能在站点 $1,2,3,4,\mathrm{5...}k-1$1,2,3,4,5...k−1切换模式。同时，活动还要求在游戏结束时必须处于夜战模式。

现在tokitsukaze的舰队从 $s$s点出发，要前往深海大本营所在的 $t$t点。请你告诉她，在难度为 $1,2,3,4,\mathrm{5...}n$1,2,3,4,5...n时，她的舰队结束游戏时受到的最小伤害。

输入描述:

第一行包括2个正整数 $n$n， $m$m，( $2\le n\le 10^5$2≤n≤105， $1\le m\le min(n\ast (n-1)/2,10^5)$1≤m≤min(n∗(n−1)/2,105))。
接下来 $m$m行，每行包括4个正整数 $u，v，a，b$u，v，a，b，( $1\le u,v\le n$1≤u,v≤n， $1\le a,b\le 10^9$1≤a,b≤109)。
最后一行包括2个正整数 $s$s， $t$t，( $1\le s,t\le n$1≤s,t≤n)。

输出描述:

请你告诉tokitsukaze，在难度为 $1,2,3,4,\mathrm{5...}n$1,2,3,4,5...n时，她的舰队处于夜战模式结束游戏受到的最小伤害。

示例1

输入

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。

示例2

输入

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

输出

1
1
1
51

说明
活动难度为1时，在编号为3的点切换模式，受到的最小伤害为1。
活动难度为2时，在编号为3的点切换模式，受到的最小伤害为1。
活动难度为3时，在编号为3的点切换模式，受到的最小伤害为1。
活动难度为4时，在编号为4的点切换模式，受到的最小伤害为51。路线是3-1-4-1。因为必须处于夜战模式结束游戏，所以在到达1后还要拐去4去切换模式。

Solution

从起点和终点分别跑最短路

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define ll long long

using namespace std;

const ll N = 1e5 + 10;
ll n, m, s, t;
ll dis1[N], dis2[N], ans[N];
bool vis[N];

struct edge
{
	ll v, day, night;
};

vector<edge> e[N];

void spfa(ll start, ll* dis, bool isday)
{
	queue<ll> q;
	memset(dis, 0x3f, sizeof dis1);
	memset(vis, 0, sizeof vis);
	q.push(start);
	dis[start] = 0;
	while (q.size())
	{
		ll u = q.front(); q.pop();
		vis[u] = false;
		for (auto i : e[u])
		{
			ll v = i.v, w;
			if (isday) w = i.day; else w = i.night;
			if (dis[u] + w < dis[v])
			{
				dis[v] = dis[u] + w;
				if (!vis[v])
					vis[v] = true, q.push(v);
			}
		}
	}
}

int main()
{
	scanf("%lld%lld", &n, &m);
	for (ll i = 1; i <= m; i++)
	{
		ll u, v, a, b;
		scanf("%lld%lld%lld%lld", &u, &v, &a, &b);
		e[u].push_back({ v, a, b });
		e[v].push_back({ u, a, b });
	}
	scanf("%lld%lld", &s, &t);
	spfa(s, dis1, true); spfa(t, dis2, false);
	memset(ans, 0x3f, sizeof ans);
	for (ll i = n; i; i--)
		ans[i] = min(ans[i + 1], dis1[i] + dis2[i]);
	for (ll i = 1; i <= n; i++)
		printf("%lld\n", ans[i]);

	return 0;
}