acwing854. Floyd finds the shortest path

Original link ：https://www.acwing.com/problem/content/856/

Unclear floyd Students of the shortest path principle can refer to this article blog：https://blog.csdn.net/weixin_52797843/article/details/121643355?spm=1001.2014.3001.5501

Catalog

Code implementation ：

 

Given a  n  A little bit  m  Directed graph of strip edge , There may be double edges and self rings in the graph , The edge weight may be negative .

Re given  k  A asked , Each query contains two integers  x  and  y, Indicates that the query is from point  x  point-to-point  y  The shortest distance , If the path doesn't exist , The output  impossible.

There is no negative weight loop in the data assurance diagram .

Input format

The first line contains three integers  n,m,k.

Next  m  That's ok , Each line contains three integers  x,y,z Indicates that there is a from point  x  point-to-point  y  The directed side of , Side length is  z.

Next  k  That's ok , Each line contains two integers  x,y, Indicates a query point  x  point-to-point  y  The shortest distance .

Output format

common  k  That's ok , Output an integer per line , Indicates the result of the inquiry , If there is no path between two points , The output  impossible.

Data range

1≤n≤200
1≤k≤n2
1≤m≤20000
The absolute value of side length involved in the figure shall not exceed  10000.

sample input ：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

sample output ：

impossible
1

Code implementation ：

#include<iostream>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m,k;
int a[310][310];
int main()
{
    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;// Diagonal distance 0
            else a[i][j]=INF;// Initialization infinity 
        }
    }
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        a[x][y]= min(a[x][y],z);
    }
    for(int k1=1;k1<=n;k1++){// Update the shortest path 
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                a[i][j]=min(a[i][j],a[i][k1]+a[k1][j]);// If the weight of other paths is smaller , The distance is shorter   to update 
            }
        }
    }
    
    while(k--)
    {
        int dx,dy;
        cin>>dx>>dy;
        if(a[dx][dy]>=15000)// The title says that the side length involved does not exceed 10000  Try to make it bigger 
        {
            cout<<"impossible"<<endl;
        }
        else cout<<a[dx][dy]<<endl;
    }
    return 0;
}