题目

Description

　　给出一个有n个顶点m条边的有向图，对于一条边长度为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

Sample Input

7 7 31 2 21 3 22 4 34 7 53 5 45 6 16 4 2

Sample Output

Data Constraint

Hint

【数据约定】

　　对于30%的数据n<=10,m<=10,

　　对于100%的数据，如题目描述

分析

我们要判断两点间是否相互连通

不单单只是两点能直接到达

间接到达也是可以的

所以我们跑一个Floyd

就能判断是否连通啦

然后要注意的一点是,我每一次跟新一次值都要放队列重新对其他点进行跟新

代码

#include
     
       #include
      
       #include
       
        #include
        
          using namespace std;int vis[201][201];int dp[201][20];int map[201][201];int flag[201];int fl[201][201];int n,m,k;vector
         
           f[201]; void spfa(){    memset(dp,0x3f,sizeof(dp));    queue
          
            q; q.push(1); dp[1][0]=0; flag[1]=1; while (!q.empty()) { int x=q.front(); q.pop(); flag[x]=0; for (int i=0;i
           
            >n>>m>>k; memset(map,0x3f,sizeof(map)); memset(fl,0x3f,sizeof(fl)); for (int i=1,x,y,z;i<=m;i++) { cin>>x>>y>>z; if (!vis[x][y]) { f[x].push_back(y); vis[x][y]=1; } map[x][y]=min(map[x][y],z); fl[x][y]=min(fl[x][y],z); } for (int kk=1;kk<=n;kk++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j&&i!=kk&&j!=kk&&fl[i][kk]+fl[kk][j]