P6961 [NEERC2017] Journey From Petersburg to Moscow

,

Description

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

Solution

先不考虑最短路的长度小于 $k$ 的情况，如果有特判一下即可。

考虑钦定第 $k$ 大的边的权值为 $val$，把每条边权重新赋值为 $\max(0,w-val)$。跑最短路以后加上 $k\times val$。

根据这条边在路径上的真实排名 $k’$，来讨论一下答案的情况：

  • 如果 $k’<k$ ，我们将第 $1$ 到 $k’$ 的权值不变，而 $k’+1$ 到 $k$ 大的边权变为 $val$，答案变大。
  • 如果 $k’=k$ ，恰好为答案。
  • 如果 $k’>k$ ，我们多算了 $k+1$ 到 $k’$ 的边，答案偏大。

考虑枚举边，取最小值就是最终答案。

三分能过，但是感觉其实不太能三分（不知道正确性）。？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 3005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,K;
int g[maxn];
int h[maxn],head=1;
struct yyy {
	int to,z,w;
	void add(int x,int y,int val) {
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn*2];
const int inf=1e15;
int dis[maxn],vis[maxn];
priority_queue<pair<int,int> >q;
int calc(int val) {
	int i,j,x;
	for (i=1;i<=n;i++) dis[i]=inf,vis[i]=0;
	q.push(mk(0,1));dis[1]=0;
	while (!q.empty()) {
		x=q.top().se;q.pop();
		if (vis[x]) continue;vis[x]=1;
		for (i=h[x];i;i=a[i].z) if (dis[a[i].to]>dis[x]+max(a[i].w-val,0ll)) {
			dis[a[i].to]=dis[x]+max(a[i].w-val,0ll);
			q.push(mk(-dis[a[i].to],a[i].to));
		}
	}
	return dis[n]+val*K;
}
signed main(void){
	freopen("1.in","r",stdin);
	int i,x,y,z;
	read(n);read(m);read(K);
	for (i=1;i<=m;i++) {
		read(x),read(y),read(z);g[i]=z;
		a[++head].add(x,y,z);
		a[++head].add(y,x,z);
	}
	sort(g+1,g+1+m);
	int tot=unique(g+1,g+1+m)-g-1;
	g[tot+1]=1e9;
	int l=-1,r=tot+1;
	while (l+3<r) {
		int lm=l+(r-l)/3,rm=l+(r-l)*2/3;
		if (calc(g[lm])>calc(g[rm])) l=lm;
		else r=rm;
	}
	int ans=inf;
	for (i=l;i<=r;i++) ans=min(ans,calc(g[i]));
	ans=min(ans,calc(0));
	printf("%lld\n",ans);
	return 0;
}