头部背景图片
Decaku 's Blog |
Decaku 's Blog |

2018ICPC南京网络赛 分层图最短路

描述:

$考虑边带权的图,已知源点和终点,如果可以使的图里的k条边\\边权变成0,最短路是多少。$


思路:

$把图分成k层,每层仍然是n个点,每层的连边方式仍然和原图相同。\\除此以外,层与层之间该如何连边?假设现在在第i层,点u和点v之间\\有一条权值w的边,对于下一层,即i+1层,u’与v’之间仍是有一条\\权为w的边,
且对于u与v’之间应该加上一条边权为0的边。$

$拆点以后在新图上跑最短路。另外此题卡SPFA,\\用优化后的dijkstra即可。$


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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
const int maxn=1200000;
const int maxm=4500000;
int t,n,m,k,a,b,c,cnt;
bool done[maxn];
ll d[maxn];
struct Edge
{
int u,v,nex;
ll w;
} edge;
Edge g[maxm];
int head[maxn];
void add(int u,int v,ll w)
{
g[cnt].u=u;
g[cnt].v=v;
g[cnt].w=w;
g[cnt].nex=head[u];
head[u]=cnt++;
}

struct HeapNode
{
int d,u;
bool operator < (const HeapNode& rhs)const
{
return d>rhs.d;
}
} node;

inline void dijkstra(int s)
{
priority_queue<HeapNode>Q;
memset(d,0x3f,sizeof(d));
d[s]=0;
memset(done,false,sizeof(done));
Q.push(HeapNode{0,s});
while(!Q.empty())
{
HeapNode x=Q.top();
Q.pop();
int u=x.u;
if(done[u]) continue;
done[u]=true;
for(int i=head[u]; i+1; i=g[i].nex)
{
if(d[g[i].v]>d[u]+g[i].w)
{
d[g[i].v]=d[u]+g[i].w;
Q.push(HeapNode{d[g[i].v],g[i].v});
}
}
}
}
inline int read()
{
char c=getchar();
int x=0,f=1;
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int main()
{
while(~scanf("%d",&t))
{
while(t--)
{
//scanf("%d%d%d",&n,&m,&k);
n=read();
m=read();
k=read();
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1; i<=m; i++)
{
//scanf("%d%d%d",&a,&b,&c);
a=read();
b=read();
c=read();
add(a,b,c);
for(int j=1; j<=k; j++)
{
add(j*n+a,j*n+b,c);
add((j-1)*n+a,j*n+b,0);
}
}
dijkstra(1);
ll ans=INF;
for(int i=1; i<=k+1; i++)
{
ans=min(ans,d[i*n]);
}
printf("%lld\n",ans);

}
}
return 0;
}
avatar Decaku 很菜但也很想carry