T3 [JLOI2011]飞行路线
期望100，实际60 我打dijkstra的时候傻了，dijkstra板子都背错了，我的vis呢？不见了！然后，考试结束，原地爆炸！！！ 题目描述
分析
本来是很简单的一道分层图最短路，看到有可以将价值变为0的东西，于是就分一下层，利用一下DP的思想。设dis[i][k]表示当前走到第i个点，用了k个能将权值变为0的“门票”，然后就用这个点来修改与它连过边的点，分成两种情况，用"门票"或者是不用"门票"，当用的"门票"大于了k，也就是将"门票"用光了时，第一种情况就跳过，直接执行第二种操作，这样就包含了所有的情况(两种情况)，想好这个思路了后就一切都交给dijkstra了，按着板子，一个一个都打了下去。最后的答案就存在了t点，也就是最后需要从起点到达的点，因为可以用k个"门票"，于是应该就在dis[n][k]中？但题目中没保证k<n，所以当k>n时这个就不对了了，答案就是最先赋值的0x3f极大值了，所以应该要从1-n遍历一遍寻找到最小值，来找到最后的答案。
code
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std
;
const int MAXN
= 1e4 + 5;
int n
,m
,k
,s
,t
,dis
[MAXN
][20],minn
= 0x3f3f3f3f;
bool vis
[MAXN
][20];
struct node
{
int u
,w
;
node(){}
node(int U
,int W
){u
= U
,w
= W
;}
friend bool operator < (node x
,node y
){return x
.w
> y
.w
;}
};
struct data
{
int u
,w
,k
;
data(){}
data(int U
,int W
,int K
){u
= U
,w
= W
,k
= K
;}
friend bool operator < (data x
,data y
){return x
.w y
.w
;}
};
vector
<node
> vec
[MAXN
];
priority_queue
<data
> Q
;
void add(int u
,int v
,int w
) {
vec
[u
].push_back(node(v
,w
));
vec
[v
].push_back(node(u
,w
));
}
void dijkstra() {
memset(dis
,0x3f,sizeof(dis
));
dis
[s
][0] = 0;
Q
.push(data(s
,0,0));
while(!Q
.empty()) {
data f
= Q
.top();
Q
.pop();
int Size
= vec
[f
.u
].size();
int use
= f
.k
;
if(vis
[f
.u
][use
]) continue;
vis
[f
.u
][use
] = 1;
for(int i
= 0;i
< Size
;i
++) {
int to
= vec
[f
.u
][i
].u
;
int wei
= vec
[f
.u
][i
].w
;
if(dis
[to
][use
+ 1] > dis
[f
.u
][use
] && use
+ 1 <= k
&& !vis
[to
][use
+ 1]) {
dis
[to
][use
+ 1] = dis
[f
.u
][use
];
Q
.push(data(to
,dis
[to
][use
+ 1],use
+ 1));
}
if(dis
[to
][use
] > dis
[f
.u
][use
] + wei
&& !vis
[to
][use
]) {
dis
[to
][use
] = dis
[f
.u
][use
] + wei
;
Q
.push(data(to
,dis
[to
][use
],use
));
}
}
}
for(int i
= 0;i
<= k
;i
++)
minn
= min(minn
,dis
[t
][k
]);
printf("%d",minn
);
return;
}
int main() {
scanf("%d %d %d %d %d",&n
,&m
,&k
,&s
,&t
);
for(int i
= 1;i
<= m
;i
++) {
int u
,v
,w
;
scanf("%d %d %d",&u
,&v
,&w
);
add(u
,v
,w
);
}
dijkstra();
return 0;
}
