隐藏
「bsoj1455」非法的摩的 - 分层图 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bsoj1455」非法的摩的 - 分层图

题目大意

    在你的强力援助下,PCY成功完成了之前的所有任务,他觉得,现在正是出去浪的大好时光。
    于是,他来到高速公路上,找到一辆摩的前往几千公里以外他心仪的那家黄焖鸡米饭。
    由于 PCY的品味异于常人,途经几百个城市的黄焖鸡米饭他都不屑一顾,他只愿意前往他心中最好的那家,但是为了一碗二十块钱的黄焖鸡米饭,他不愿意花上几千块的路费,他希望路费尽量少。高速路上的警察叔叔被他的行为所打动,于是在多方协调下,最多$K$条城市之间的高速收费站愿意免费为PCY放行(可以任意选择)。
    显然,PCY已经筋疲力尽,不想再动用自己的数学天才来计算他可以花费的最小路费,因此他希望你可以帮他最后一次,他说他可以请你吃大碗的黄焖鸡米饭,还可以加一瓶豆奶。
    现在给你$N$个城市(编号为$0\ldots N-1$),$M$条道路,和每条高速公路的花费$W_i$ ,以及题目所描述的$K$。PCY想从城市$S$到城市$T$,因为他对$T$城市的黄焖鸡米饭情有独钟。


题目分析

分层图裸题,直接设二维状态进行Dijkstra
似乎SPFA被卡。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=10005;
int n,m,s,t,k,dist[maxn][15],vst[maxn][15];
struct QueNode {
int d,u,v;
bool operator < (const QueNode& b) const {
return d>b.d;
}
};
struct Edge {
int from,to,dist;
};
vector<Edge>edges[maxn];
void AddEdge(int x,int y,int v) {
edges[x].push_back((Edge) {
x,y,v
});
}
void Dijkstra(int s) {
for(int i=1; i<=n; i++)
for(int j=0; j<=k; j++)
dist[i][j]=0x7fffffff/2;
dist[s][0]=0;
priority_queue<QueNode>Q;
Q.push((QueNode) {
0,s,0
});
while(!Q.empty()) {
QueNode Now=Q.top();
Q.pop();
if(vst[Now.u][Now.v])continue;
vst[Now.u][Now.v]=1;
for(Edge& e:edges[Now.u]) {
int Next=e.to;
if(dist[Next][Now.v]>dist[Now.u][Now.v]+e.dist) {
dist[Next][Now.v]=dist[Now.u][Now.v]+e.dist;
Q.push((QueNode) {
dist[Next][Now.v],Next,Now.v
});
}
if(Now.v<k&&dist[Next][Now.v+1]>dist[Now.u][Now.v]) {
dist[Next][Now.v+1]=dist[Now.u][Now.v];
Q.push((QueNode) {
dist[Next][Now.v+1],Next,Now.v+1
});
}
}
}
}
int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
s=Get_Int();
t=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
AddEdge(x,y,v);
AddEdge(y,x,v);
}
Dijkstra(s);
int ans=0x7fffffff/2;
for(int i=0; i<=k; i++)ans=min(ans,dist[t][i]);
printf("%d\n",ans);
return 0;
}
姥爷们赏瓶冰阔落吧~