最短路

#include<bits/stdc++.h>
using namespace std;
int g[205][205];
int main(){
    memset(g,0x3f,sizeof g);
    int n,m,k;cin>>n>>m>>k;
    while(m--){
        int x,y,z;cin>>x>>y>>z;
        g[x][y]=z;
    }
    
    //最短路径的处理，floyd 佛洛依德最短路办法
    for(int p=1;p<=n;p++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                g[i][j]=min(g[i][p]+g[p][j],g[i][j]);
            }
        } 
    }
    while(k--){
        int x,y;cin>>x>>y;
        if(g[x][y]==0x3f3f3f3f) cout<<"impossible"<<endl;
        else cout<<g[x][y]<<endl; 
    }
    return 0;
}
 

 最短路的概念

在一个图中有 n个点、m条边。边有权值，权值可正可负。边可能是有向的，也可能是无向的。

给定两个点，起点是s，终点是t，在所有能连接s和t的路径中寻找边的权值之“和” 最小的路径，这就是最短路径问题

最短路常包含两种：

单源最短路：从单个节点出发，到所有节点的最短路
多源最短路：整个图中所有点到其他点的最短路

对于无权图：

一次BFS可求得最短路

对于有权图：