题目描述

给定一个 n 个点 m 条边构成的无重边和自环的无向连通图。

点的编号为 1∼n。

请问：

从 1 到 n 的最短距离。
去掉 k 条边后，从 1 到 n 的最短距离。

样例

输入
1
4 4 1
1 2 1
2 3 1
3 4 1
1 4 1
4
输出
1
3

floyd裸题

C++ 代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
# include<iostream>
# include<algorithm>
# include<cmath>
# include<cstdio>
# include<set>
# include<stack>
# include<queue> 
# include<map>
# include<string>
# include<cstring> 
#include<limits.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int > PII; 
const int mod=100000;
const int MAX=2e6+10;
const int Time=86400;
const int X=131;
const ll inf=0x3f3f3f3f;

int n,m,k,head[MAX],tot,a[305][305],t;
struct Node{
    int x,y,z;
    int flag;
}b[MAX];
void floyd(){
    for(int k=1;k<=n;k++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
       a[i][j] = min(a[i][k]+a[k][j],a[i][j]);
}
int main(){  
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      if(i==j) a[i][j] = 0;
       else a[i][j] = inf; 

    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y] = a[y][x] = min(a[x][y],z);
        b[i]={x,y,z,1};
    }

    floyd();

    cout<<a[1][n]<<"\n";

    while(k--){
        int x;
        cin>>x;
        b[x].flag = 0;
    }

    for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
      if(i==j) a[i][j] = 0;
       else a[i][j] = inf; 

    for(int i=1;i<=m;i++){
       if(b[i].flag == 0) continue;
       a[b[i].x][b[i].y] = a[b[i].y][b[i].x] = min(a[b[i].x][b[i].y],b[i].z ); 
    }
    floyd();

    if(a[1][n] > inf/2) cout<<"-1\n";
     else cout<<a[1][n]<<"\n";
 }
    return 0;
}