bzoj 4681 旅行

Posted on | Views:

最短路.

  • 这类点,边数目比较少,却有一些奇奇怪怪的条件的最短路,大多都是拆点.然而实现时并不需要真的拆点,只需要在做最短路的时候给 $dis$ 多加几维即可.
  • 考虑暴力做法,应该是 $dfs$ 找出每一条路径,贪心地将不在路径上最短的边与在路径上最长的边交换,最多 $k$ 次.
  • 然而路径条数可以被随便搞到指数级.
  • 沿用贪心的思想,最后最优路径中的边一定会包含全部前 $L$ 小的边,可以将边排序,枚举 $L$ ,结合最短路解决.
  • 设 $f(u,j,k)$ 表示从 $1$ 到 $u$ ,路径上有 $j$ 条前 $L$ 小的边,交换了 $k$ 次时的最短路.转移时分当前边不在前 $L$ 小与当前边在前 $L$ 小,用 $Dijkstra$ 转移即可.

注意正反加了两条边,实际排名需 $/2$ .

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=151;
int ans=0x7fffffff;
int ecnt=0,head[MAXN],nx[MAXN<<1],to[MAXN<<1];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
struct Edge
{
	int u,v,len;
	bool operator < (const Edge &rhs) const
	{
		return len<rhs.len;
	}
}E[MAXN];
struct node
{
	int u,j,k,dis;
	bool operator < (const node &rhs) const
	{
		return dis>rhs.dis;
	}
	node(int u=0,int j=0,int k=0,int dis=0):u(u),j(j),k(k),dis(dis) {}
};
int N,M,K;
int dis[MAXN][MAXN][MAXN],vis[MAXN][MAXN][MAXN];
priority_queue<node> q;
void Dijkstra(int L)
{
	memset(vis,0,sizeof vis);
	memset(dis,63,sizeof dis);
	node p=node(1,0,0,0);
	dis[1][0][0]=0;
	q.push(p);
	while(!q.empty())
	{
		p=q.top();
		q.pop();
		int u=p.u,j=p.j,k=p.k;
		if(vis[u][j][k])
			continue;
		vis[u][j][k]=1;
		for(int i=head[u];i;i=nx[i])
		{
			int v=to[i];
			if(i<=L*2)
			{
				if(j<L && dis[v][j+1][k]-dis[u][j][k]>E[j+1].len)
				{
					dis[v][j+1][k]=dis[u][j][k]+E[j+1].len;
					p=node(v,j+1,k,dis[v][j+1][k]);
					q.push(p);
				}
			}
			else
			{
				if(j<L && k<K && dis[v][j+1][k+1]-dis[u][j][k]>E[j+1].len)
				{
					dis[v][j+1][k+1]=dis[u][j][k]+E[j+1].len;
					p=node(v,j+1,k+1,dis[v][j+1][k+1]);
					q.push(p);
				}
				if(dis[v][j][k]-dis[u][j][k]>E[(i+1)>>1].len)
				{
					dis[v][j][k]=dis[u][j][k]+E[(i+1)>>1].len;
					p=node(v,j,k,dis[v][j][k]);
					q.push(p);
				}
			}
		}
	}
	for(int i=0;i<=K;++i)
		ans=min(ans,dis[N][L][i]);
}
int main()
{
	N=read(),M=read(),K=read();
	for(int i=1;i<=M;++i)
	{
		E[i].u=read();
		E[i].v=read();
		E[i].len=read();
	}
	sort(E+1,E+1+M);
	for(int i=1;i<=M;++i)
	{
		addedge(E[i].u,E[i].v);
		addedge(E[i].v,E[i].u);
	}
	for(int i=0;i<=M;++i)
		Dijkstra(i);
	cout<<ans<<endl;
	return 0;
}