分类：
多源路径算法。
角色：
1 .寻求最短路。 2 .判断一张图中的两点是否相连。
优点：
实现极其简单
坏处：
只有在数据规模较小，时空复杂性都允许的情况下才能使用(NOIP恐怕不会发出)。
思想：
3层循环，第1层列举中间点k，第2层和第3层列举2个端点I、j。 将dis[i][j] dis[i][k] dis[k][j]更新为dis[i][k] dis[k][j] (如果存在)。 (原理还很明白。
实现：
(a )初始化)如果点I，j有边缘连接，则dis[i][j]=w[i][j]。 如果没有连接，则dis[I][j]=0x7ffffff(int极限值)表示两点没有连接(或被认为是分离的)。
(b )算法代码：
for(intk=1； k=n； k//枚举中间点(必须放在最外层) for ) intI=1； i=n； (I )//枚举端点Iif ) I！=k ) for(intj=1； j=n； j//枚举端点JIF(I！=j j！=kdis [ I ] [ j ] dis [ I ] [ k ] dis [ k ] [ j ] ] dis [ I ] [ j ]=dis [ I ] [ k ] dis [ k ] [ j ]；
) c )算法的结束：从dis[i][j]中得到的是从I到j的最短路径。
Floyed算法的变形：
没有边权的图的情况下，连接的2点间的距离为dis[i][j]=true，没有连接的2点为dis[i][j]=false，使用Floyed算法的变形：
for(intk=1； k=n； k//枚举中间点for(intI=1； i=n； (I )//枚举端点Iif ) I！=k ) for(intj=1； j=n； j//枚举端点JIF(I！=j j！=k ) dis [ I ] [ j ]=dis [ I ] [ j ]|(dis [ I ] [ k ] dis [ k ] [ j ] )； (判断是否连接)
用这种方法可以判断一张图中的两点是否相连。
例题：
一，
最短路径问题
给你n个点。 没有m条有向边。 每一边都有长度d和费用p。 给你起点s终点t。 要求输出从起点到终点的最短距离及其费用。 如果最短距离有多条路线，则输出费用最高。
输入
输入n，m。 点的编号是1~n，之后是m行。 每行a、b、d、p的数量为4个，表示a和b之间有一条边，其长度为d，费用为p。 最后一行是两个数s，t； 起点s，终点。 n和m为0时输入结束。
(1n=1000，0m 100000，s！=t )
Output
输出一行有两个个数、最短距离及其费用。
样品输入
3 21 2 5 62 3 4 51 30 0 Sample Output
911 # include iostream # include stdio.h # include algorithm # include string.h # include math.husingnamespacestd； #define INF0x3f3f3f3fint n，m，s，t； int a、b、d、p； int map[1010][1010]； int money[1010][1010]； int main () while(~scanf ) (%d )，n，m ) ) if ) n==0m==0) break； for(intI=1； i=n； I ) for(intj=1； j=n； j ) if(I==j ) map[i][j]=0； else map[i][j]=INF； for(intI=1； i=m； I ) scanf('%d%d%d%d )、a、b、d、p )； map[a][b]=d； money[a][b]=p； }scanf('%d%d )，s，t )； for(intk=1； k=n； k ) for(intI=1； i=n； I ) for(intj=1； j=n； j ) {
if(map[i][j]>map[i][k]+map[k][j]){ map[i][j]=map[i][k]+map[k][j]; money[i][j]=money[i][k]+money[k][j]; } } cout << map[s][t] << " " << money[s][t] << endl; } //cout << "Hello world!" << endl; return 0;}https://blog.csdn.net/weixin_43272781/article/details/83307686
二、Einbahnstrasse
Einbahnstra e (German for a one-way street) is a street on which vehicles should only move in one direction. One reason for having one-way streets is to facilitate a smoother flow of traffic through crowded areas. This is useful in city centers, especially old cities like Cairo and Damascus. Careful planning guarantees that you can get to any location starting from any point. Nevertheless, drivers must carefully plan their route in order to avoid prolonging their trip due to one-way streets. Experienced drivers know that there are multiple paths to travel between any two locations. Not only that, there might be multiple roads between the same two locations. Knowing the shortest way between any two locations is a must! This is even more important when driving vehicles that are hard to maneuver (garbage trucks, towing trucks, etc.)
You just started a new job at a car-towing company. The company has a number of towing trucks parked at the company's garage. A tow-truck lifts the front or back wheels of a broken car in order to pull it straight back to the company's garage. You receive calls from various parts of the city about broken cars that need to be towed. The cars have to be towed in the same order as you receive the calls. Your job is to advise the tow-truck drivers regarding the shortest way in order to collect all broken cars back in to the company's garage. At the end of the day, you have to report to the management the total distance traveled by the trucks.
Input
Your program will be tested on one or more test cases. The first line of each test case specifies three numbers (N , C , and R ) separated by one or more spaces. The city has N locations with distinct names, including the company's garage. C is the number of broken cars. R is the number of roads in the city. Note that 0 < N < 100 , 0<=C < 1000 , and R < 10000 . The second line is made of C + 1 words, the first being the location of the company's garage, and the rest being the locations of the broken cars. A location is a word made of 10 letters or less. Letter case is significant. After the second line, there will be exactly R lines, each describing a road. A road is described using one of these three formats:
A -v -> B
A <-v - B
A <-v -> B
A and B are names of two different locations, while v is a positive integer (not exceeding 1000) denoting the length of the road. The first format specifies a one-way street from location A to B , the second specifies a one-way street from B to A , while the last specifies a two-way street between them. A , ``the arrow", and B are separated by one or more spaces. The end of the test cases is specified with a line having three zeros (for N , C , and R .)
The test case in the example below is the same as the one in the figure.
Output
For each test case, print the total distance traveled using the following format:
k . V
Where k is test case number (starting at 1,) is a space, and V is the result.
Sample Input
4 2 5NewTroy Midvale MetrodaleNewTroy <-20-> MidvaleMidvale --50-> BakerlineNewTroy <-5-- BakerlineMetrodale <-30-> NewTroyMetrodale --5-> Bakerline0 0 0Sample Output
1. 80 /**@Author: STZG*@Language: C++*/#include <bits/stdc++.h>#include<iostream>#include<algorithm>#include<cstdlib>#include<cstring>#include<cstdio>#include<string>#include<vector>#include<bitset>#include<queue>#include<deque>#include<stack>#include<cmath>#include<list>#include<map>#include<set>//#define DEBUGusing namespace std;typedef long long ll;const int N=10000;const double PI = acos(-1.0);const double EXP = 1E-8;const int INF = 0x3f3f3f3f;int t,n,c,r,m;char s1[100],s2[100],c1,c2;char str[1005][100];int a[105][105];int main(){#ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout);#endif ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T=0; while(scanf("%d%d%d",&n,&c,&r)!=EOF&&n+c+r){ map<string,int>M; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ a[i][j]=INF; } } for(int i=0;i<=c;i++){ scanf("%s",str[i]); } int cnt=0; for(int i=1;i<=r;i++){ scanf("%s %c-%d-%c %s",s1,&c1,&t,&c2,s2); if(!M[s1]) M[s1]=++cnt; if(!M[s2]) M[s2]=++cnt; int x=M[s1],y=M[s2]; if(c1=='<'&&a[y][x]>t) a[y][x]=t; if(c2=='>'&&a[x][y]>t) a[x][y]=t; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){// if(a[j][k]>a[j][i]+a[i][k])// a[j][k]=a[j][i]+a[i][k]; a[j][k]=min(a[j][k],a[j][i]+a[i][k]); } } } ll ans=0; for(int i=1;i<=c;i++){ ans+=a[M[str[0]]][M[str[i]]]+a[M[str[i]]][M[str[0]]]; } printf("%d. %lldn",++T,ans); } //cout << "Hello world!" << endl; return 0;}https://blog.csdn.net/weixin_43272781/article/details/84943350