【题解】【最短路】行动!行动!

xiaoxiao2021-02-28  4

行动!行动!

Description

大CX国的大兵Jack接到一项任务:敌方占领了n座城市(编号0~n-1),有些城市之间有双向道路相连。Jack需要空降在一个城市S,并徒步沿那些道路移动到T城市。虽然Jack每从一个城市到另一个城市都会受伤流血,但大CX国毕竟有着“过硬”的军事实力,它不仅已经算出Jack在每条道路上会损失的血量,还给Jack提供了k个“简易急救包”,一个包可以让Jack在一条路上的流血量为0。Jack想知道自己最少会流多少血,不过他毕竟是无脑的大兵,需要你的帮助。

Input

第一行有三个整数n,m,k,分别表示城市数,道路数和急救包个数。

第二行有两个整数,S,T。分别表示Jack空降到的城市编号和最终要到的城市。

接下来有m行,每行三个整数a,b,c,表示城市a与城市b之间有一条双向道路。

Output

Jack最少要流的血量。

Sample Input

5 6 1 0 3 3 4 5 0 1 5 0 2 100 1 2 5 2 4 5 2 4 3

Sample Output

8

HINT

【说明】

对于30%的数据,2<=n<=50,1<=m<=300,k=0;

对于50%的数据,2<=n<=600,1<=m<=6000,0<=k<=1;

对于100%的数据,2<=n<=10000,1<=m<=50000,0<=k<=10.

题解:

30分做法:

留意到有30%的数据k=0,所以直接SPFA

50分做法:

对于k=1的数据,起点跑一次SPFA,终点跑一次SPFA,然后枚举每条边a->b,用起点到a的最短路+终点到b的最短路更新ans即可。

100分做法:

把SPFA的距离数组改成2维的,令d[i][j]代表起点到点i用了j个急救包后的最短路。

然后SPFA的松弛改成两种情况:用急救包和不用。

最后的答案就是min{d[t][i]}(0<=i<=k)

这样就成功解决了本题。

代码:

#include <iostream> #include <vector> #include <cstdio> #include <algorithm> #include <queue> #include <cstring> using namespace std; #define MAXN 10001 #define MAXK 11 vector<int> edge[MAXN],we[MAXN]; int d[MAXN][MAXK],n,m,k; struct node{ int city,used; node():city(0),used(0){} node(int a,int b):city(a),used(b){} }; void spfa(int x) { queue<node> q; q.push(node(x,0)); for(int i=1;i<=n;++i) { for(int j=0;j<=k;++j) d[i][j]=1000000000; } for(int i=0;i<=k;++i) d[x][i]=0; do { node u=q.front(); q.pop(); for(unsigned i=0;i<edge[u.city].size();++i) { int v=edge[u.city][i],w=we[u.city][i]; if(d[v][u.used]>d[u.city][u.used]+w) { d[v][u.used]=d[u.city][u.used]+w; q.push(node(v,u.used)); } if(u.used<k && d[v][u.used+1]>d[u.city][u.used]) { d[v][u.used+1]=d[u.city][u.used]; q.push(node(v,u.used+1)); } } } while(!q.empty()); } int main() { int u,v,w,s,t; scanf("%d%d%d%d%d",&n,&m,&k,&s,&t); ++s; ++t; for(int i=1;i<=m;++i) { scanf("%d%d%d",&u,&v,&w); ++u; ++v; edge[u].push_back(v); we[u].push_back(w); edge[v].push_back(u); we[v].push_back(w); } spfa(s); int ans=2147483647; for(int i=0;i<=k;++i) { ans=min(ans,d[t][i]); } printf("%d\n",ans); }

转载请注明原文地址: https://www.6miu.com/read-1150093.html

最新回复(0)