洛谷题解-[ABC325E] Our clients, please wait a moment

https://www.luogu.com.cn/problem/AT_abc325_e

题目描述

ある国には都市が N N N 個あります。
あなたは、都市 1 1 1 にある営業所から 0 0 0 個以上の都市を経由して都市 N N N にある訪問先へ移動しようとしています。
移動手段は社用車と電車の 2 2 2 種類があります。都市 i i i から都市 j j j へ移動するときの所要時間は以下の通りです。

• 社用車を使った場合 : Di,j × A D_{i,j}\ \times\ A Di,j​ × A 分
• 電車を使った場合 : Di,j × B + C D_{i,j}\ \times\ B\ +\ C Di,j​ × B + C 分

ただし、社用車から電車に乗り換えることはできますが、電車から社用車に乗り換えることはできません。
また、乗り換えは各都市のみで行え、乗り換えに時間はかかりません。

都市 1 1 1 から都市 N N N に移動するのにかかる時間は最短で何分ですか？

输入格式

入力は以下の形式で標準入力から与えられる。

N N N A A A B B B C C C D1,1 D_{1,1} D1,1​ D1,2 D_{1,2} D1,2​ … \ldots … D1,N D_{1,N} D1,N​ D2,1 D_{2,1} D2,1​ D2,2 D_{2,2} D2,2​ … \ldots … D2,N D_{2,N} D2,N​ ⋮ \vdots ⋮ DN,1 D_{N,1} DN,1​ DN,2 D_{N,2} DN,2​ … \ldots … DN,N D_{N,N} DN,N​

输出格式

答えを整数として出力せよ。

题意翻译

题目描述

一个国家里有 nnn 个城市。
你需要从 111 号城市旅行到 nnn 号城市。
你有坐车和坐火车两种通行方式，对于从城市 iii 到城市 jjj ：

• 坐车会花费 Di,j×AD_{i,j} \times ADi,j​×A 分钟
• 坐火车会花费 Di,j×B+CD_{i,j} \times B+CDi,j​×B+C 分钟

你可以在不花费任何时间的情况下从坐车切换为坐火车，但不能从坐火车切换为坐车。

问从城市 111 到城市 nnn 最少需要几分钟？

输入输出样例

4 8 5 13
0 6 2 15
6 0 3 5
2 3 0 13
15 5 13 0

78

3 1 1000000 1000000
0 10 1
10 0 10
1 10 0

1

5 954257 954213 814214
0 84251 214529 10017 373342
84251 0 91926 32336 164457
214529 91926 0 108914 57762
10017 32336 108914 0 234705
373342 164457 57762 234705 0

168604826785

说明/提示

制約

• 2 ≤ N ≤ 1000 2\ \leq\ N\ \leq\ 1000 2 ≤ N ≤ 1000
• 1 ≤ A, B, C ≤ 106 1\ \leq\ A,\ B,\ C\ \leq\ 10^6 1 ≤ A, B, C ≤ 106
• Di,j ≤ 106 D_{i,j}\ \leq\ 10^6 Di,j​ ≤ 106
• Di,i = 0 D_{i,i}\ =\ 0 Di,i​ = 0
• Di,j = Dj,i > 0 D_{i,j}\ =\ D_{j,i}\ >\ 0 Di,j​ = Dj,i​ > 0 (i ≠ j) (i\ \neq\ j) (i = j)
• 入力される数値はすべて整数

Sample Explanation 1

以下のように移動することで合計 78 78 78 分で都市 1 1 1 から都市 4 4 4 に移動することができます。 - 都市 1 1 1 から都市 3 3 3 まで社用車で移動する。この移動には 2 × 8 = 16 2\ \times\ 8\ =\ 16 2 × 8 = 16 分かかる。 - 都市 3 3 3 から都市 2 2 2 まで社用車で移動する。この移動には 3 × 8 = 24 3\ \times\ 8\ =\ 24 3 × 8 = 24 分かかる。 - 都市 2 2 2 から都市 4 4 4 まで電車で移動する。この移動には 5 × 5 + 13 = 38 5\ \times\ 5\ +\ 13\ =\ 38 5 × 5 + 13 = 38 分かかる。 78 78 78 分未満の時間で都市 1 1 1 から都市 4 4 4 に移動することはできません。

最短路求值注意数据范围，可能开longlong，但是最短路函数内部的变量关于权值的就也要开longlong，详解见下

你可以在不花费任何时间的情况下从坐车切换为坐火车，但不能从坐火车切换为坐车。

那么我们可以枚举换乘点，然后正向跑乘车，反向从n开始跑乘火车，然后枚举换乘点，正向跑的车+反向跑的火车，就是答案，取个min即可

但是被卡了很久，大数据总是输出负数，原因看注释

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;
struct node
{
	int v;
	long long w;
	bool operator <(const node &A) const
	{
		return w>A.w;
	};
};
vector<node> a[N], a2[N];
priority_queue<node> q;
int n, vis[N];
long long A, B, C, w1, dis[N], dis2[N], ans=0;
long long min2(long long a, long long b)
{
	if (a<b) return a;
	return b;
}
void dij(int s)
{
	memset(dis, 63, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s]=0, q.push({s, 0});
	
	while (!q.empty())
	{
		int u=q.top().v;
		q.pop();
		
		if (vis[u]) continue;
		vis[u]=1;
		
		for (int i=0; i<a[u].size(); i++)
		{
			long long v=a[u][i].v, w=a[u][i].w; //注意开w也要开longlong!!!
			if (!vis[v] && dis[v]>dis[u]+w)
			{
				dis[v]=dis[u]+w;
				q.push({v, dis[v]});
			}
		}
	}
}
void dij2(int s)
{
	memset(dis2, 63, sizeof dis2);
	memset(vis, 0, sizeof vis);
	dis2[s]=0, q.push({s, 0});
	
	while (!q.empty())
	{
		int u=q.top().v;
		q.pop();
		
		if (vis[u]) continue;
		vis[u]=1;
		
		for (int i=0; i<a2[u].size(); i++)
		{
			long long v=a2[u][i].v, w=a2[u][i].w; //注意开w也要开longlong!!!
			if (!vis[v] && dis2[v]>dis2[u]+w)
			{
				dis2[v]=dis2[u]+w;
				q.push({v, dis2[v]});
			}
		}
	}
}
int main()
{
	scanf("%d%lld%lld%lld", &n, &A, &B, &C);
	for (int i=1; i<=n; i++)
		for (int j=1; j<=n; j++)
		{
			scanf("%lld", &w1);
			a[i].push_back({j, w1*A});
			a2[j].push_back({i, w1*B+C}); //反向建
		}
	dij(1);
	dij2(n);
	
	ans=dis[0];
	for (int i=1; i<=n; i++)
		ans=min(ans, dis[i]+dis2[i]); //正反跑
	
	printf("%lld", ans);
	return 0;
}