Travel

Description

---

　　给出一个有 个顶点 条边的有向图，对于一条边长度为len的边有两种走法。 　　1、如果a和b可以互达，则走过这条边的时间为len 　　2、如果a和b不可以互达，则走过这条边的时间为2*len 　　现在给出一个k，问，从顶点1到顶点n，满足第二种走法不超过k次的最短时间是多少。

Input

---

　　第一行有3个整数n,m,k(1<=n<=100,1<=m<=10000,0<=k<=10),表示有n个顶点，m条边。 　　接下来有m行，每行有3个整数xi,yi,leni(1<=xi,yi<=n,1<=leni<=10000)，表示长度为leni的有向边。 　　注意，两个点可能有多条边连接。

Output

---

　　一行一个整数，表示最短时间。 　　如果没有满足题目条件的路径，则输出-1

Hint

---

[数据约定]

　　对于30%的数据n<=10,m<=10, 　　对于100%的数据，如题目描述

Analysis

---

spfa+分层图，n很小所以floyd判连通，对于不能互达的点之间的边*2 dis[i][j] 表示走到点i走了j次第二种走法的最短路径

Code

---

#include <stdio.h> #include <queue> using namespace std; struct status { int x,k; }; queue<status>q; bool v[1001][1001]; int dis[1001][1001],f[1001][1001],a[1001][1001]; int main() { int n,m,k; scanf("%d%d%d",&n,&m,&k); for (int i=0;i<=n;i++) for (int j=0;j<=n;j++) { f[i][j]=1<<28-1; a[i][j]=1<<28-1; } for (int i=1;i<=m;i++) { int x,y,w; scanf("%d%d%d",&x,&y,&w); if (a[x][y]>w) a[x][y]=w; f[x][y]=a[x][y]; } for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j&&i!=k&&i!=k&&f[i][k]+f[k][j]<f[i][j]) f[i][j]=f[i][k]+f[k][j]; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (f[j][i]==f[0][0]&&a[i][j]!=a[0][0]) a[i][j]*=2; for (int i=0;i<=n;i++) for (int j=0;j<=k;j++) dis[i][j]=1<<28-1; dis[1][0]=0; q.push((status){1,0}); v[1][0]=true; while (q.size()) { status s=q.front(); int now=s.x; int tmp=s.k; q.pop(); for (int i=1;i<=n;i++) if (a[now][i]!=a[0][0]) { if (f[i][now]==f[0][0]) if (dis[now][tmp]+a[now][i]<dis[i][tmp+1]&&tmp<k) { dis[i][tmp+1]=dis[now][tmp]+a[now][i]; if (!v[i][tmp+1]) { v[i][tmp+1]=true; q.push((status){i,tmp+1}); } } if (f[i][now]!=f[0][0]) if (a[now][i]+dis[now][tmp]<dis[i][tmp]) { dis[i][tmp]=a[now][i]+dis[now][tmp]; if (!v[i][tmp]) { v[i][tmp]=true; q.push((status){i,tmp}); } } } v[now][tmp]=false; } int ans=1<<28-1; for (int i=0;i<=k;i++) if (dis[n][i]<ans) ans=dis[n][i]; if (ans>=a[0][0]) ans=-1; printf("%d\n",ans); return 0; }