1、Floyd算法
【题目描述】 平面上有n个点（n<=100），每个点的坐标均在-10000~10000之间。其中的一些点之间有连线。
若有连线，则表示可从一个点到达另一个点，即两点间有通路，通路的距离为两点间的直线距离。现在的任务是找出从一点到另一点之间的最短路径。
【输入】 共n+m+3行，其中:
第一行为整数n。
第2行到第n+1行（共n行） ，每行两个整数x和y，描述了一个点的坐标。
第n+2行为一个整数m，表示图中连线的个数。
此后的m 行，每行描述一条连线，由两个整数i和j组成，表示第i个点和第j个点之间有连线。
最后一行：两个整数s和t，分别表示源点和目标点。
【输出】 一行，一个实数（保留两位小数），表示从s到t的最短路径长度。
【输入样例】 5 0 0 2 0 2 2 0 2 3 1 5 1 2 1 3 1 4 2 5 3 5 1 5 【输出样例】 3.41
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N=105;
int a[N][3];// 一维存储点的编号，二维存储点的x、y坐标
double dis[N][N];
int main()
{
int n,m,s,t,x,y;
memset(dis,0x7f,sizeof(dis));// double 数组初始化用 0x7f
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i][1]>>a[i][2];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
dis[y][x]=dis[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));// 距离的初始化
}
cin>>s>>t;
// 算法主体
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if((i!=j) && (i!=k) && (j!=k) && (dis[i][k]+dis[k][j]<dis[i][j]))
{
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
printf("%.2lf",dis[s][t]);
return 0;
}2、Dijkstra算法
题目同上
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const double INF=1e30;
const int N=105;
int n,m,S,T,x,y;
int a[N][3];
double dis[N][N];
double d[N];
bool vis[N]={false};
void dijkstra(int s,int t)
{
memset(d,0x7f,sizeof(d));
d[s]=0;// 起点到自身的距离为0
for(int i=1;i<=n;i++)
{
int u=-1;
double MIN=INF;
for(int j=1;j<=n;j++)
{
if(!vis[j]&&d[j]<MIN)
{
u=j;
MIN=d[j];
}
}
if(u==-1)return;
vis[u]=true;
for(int v=1;v<=n;v++)
{
if(!vis[v]&&dis[u][v]<INF&&d[u]+dis[u][v]<d[v])
{
d[v]=d[u]+dis[u][v];
}
}
}
}
int main()
{
memset(dis,0x7f,sizeof(dis));
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i][1]>>a[i][2];
}
cin>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
dis[y][x]=dis[x][y]=sqrt(pow(double(a[x][1]-a[y][1]),2)+pow(double(a[x][2]-a[y][2]),2));
}
cin>>S>>T;
dijkstra(S,T);
printf("%.2lf",d[T]);
return 0;
}3、牛的旅行-Floyd算法
【题目描述】 农民John的农场里有很多牧区。有的路径连接一些特定的牧区。一片所有连通的牧区称为一个牧场。但是就目前而言，你能看到至少有两个牧区不连通。现在，John想在农场里添加一条路径 ( 注意，恰好一条 )。对这条路径有这样的限制：一个牧场的直径就是牧场中最远的两个牧区的距离 ( 本题中所提到的所有距离指的都是最短的距离 )。考虑如下的两个牧场，图１是有5个牧区的牧场，牧区用“*”表示，路径用直线表示。每一个牧区都有自己的坐标：
图１所示的牧场的直径大约是12.07106, 最远的两个牧区是A和E，它们之间的最短路径是A-B-E。
这两个牧场都在John的农场上。John将会在两个牧场中各选一个牧区，然后用一条路径连起来，使得连通后这个新的更大的牧场有最小的直径。注意，如果两条路径中途相交，我们不认为它们是连通的。只有两条路径在同一个牧区相交，我们才认为它们是连通的。
现在请你编程找出一条连接两个不同牧场的路径，使得连上这条路径后，这个更大的新牧场有最小的直径。
【输入】 第 1 行：一个整数N (1 <= N <= 150), 表示牧区数；
第 2 到 N+1 行：每行两个整数X，Y ( 0 <= X，Y<= 100000 )， 表示N个牧区的坐标。每个牧区的坐标都是不一样的。
第 N+2 行到第 2*N+1 行：每行包括N个数字 ( 0或1 ) 表示一个对称邻接矩阵。
例如，题目描述中的两个牧场的矩阵描述如下：
A B C D E F G H A 0 1 0 0 0 0 0 0 B 1 0 1 1 1 0 0 0 C 0 1 0 0 1 0 0 0 D 0 1 0 0 1 0 0 0 E 0 1 1 1 0 0 0 0 F 0 0 0 0 0 0 1 0 G 0 0 0 0 0 1 0 1 H 0 0 0 0 0 0 1 0 输入数据中至少包括两个不连通的牧区。
【输出】 只有一行，包括一个实数，表示所求答案。数字保留六位小数。
【输入样例】 8 10 10 15 10 20 10 15 15 20 15 30 15 25 10 30 10 01000000 10111000 01001000 01001000 01110000 00000010 00000101 00000010 【输出样例】 22.071068
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int N=155;
int n;
double INF=1e12;
double minx=1e20;
double x[N];
double y[N];
double m[N];
double dis[N][N];
double fun(int i,int j)
{
return sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
}
int main()
{
cin>>n;
char c;
for(int i=1;i<=n;i++)
{
cin>>x[i]>>y[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
cin>>c;
if(c=='1')
{
dis[i][j]=fun(i,j);
}else
{
dis[i][j]=INF;
}
}
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&i!=k&&j!=k)
{
if(dis[i][k]<INF-1&&dis[k][j]<INF-1)
{
if(dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
}
}
memset(m,0,sizeof(m));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(dis[i][j]<INF-1&&m[i]<dis[i][j])
{
m[i]=dis[i][j];
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&dis[i][j]>INF-1)// double型数据的大小比较一般不使用==
{
double temp=fun(i,j);
if(m[i]+m[j]+temp<minx)
{
minx=m[i]+m[j]+temp;
}
}
}
}
for(int i=1;i<=n;i++)
{
if(m[i]>minx)
{
minx=m[i];
}
}
printf("%.6lf",minx);
return 0;
}4、香甜的黄油--spfa算法
【题目描述】 农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1≤N≤500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。
农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。
农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。
【输入】 第一行: 三个数：奶牛数N，牧场数P（2≤P≤800），牧场间道路数C(1≤C≤1450)。
第二行到第N+1行: 1到N头奶牛所在的牧场号。
第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距（1≤D≤255），当然，连接是双向的。
【输出】 一行 输出奶牛必须行走的最小的距离和。
【输入样例】 3 4 5 2 3 4 1 2 1 1 3 5 2 3 7 2 4 3 3 4 5 【输出样例】 8
#include<iostream>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int INF=0x7fffffff;
const int N=805;// 牧场的最大数量
int cow[510];//奶牛所在的牧场编号
int n,p,c;
struct Node
{
int v;//边的终点编号
int w;//边权，即两个牧场间的距离
Node(int _v,int _w):v(_v),w(_w){};//构造函数
};
vector<Node> Adj[N];// 建立邻接表，数组中的每一个元素都是vector，vector的每个元素都是Node类型
int d[N];//源点到各点最短路径
int num[N];//各点入队次数
bool inq[N];//是否在队列中
bool spfa(int s)//源点
{
//初始化
fill(d,d+N,INF);
memset(num,0,sizeof(num));
memset(inq,false,sizeof(inq));
// 建立队列
queue<int>q;
//对源点操作
d[s]=0;
q.push(s);
inq[s]=true;
num[s]++;
while(!q.empty())
{
int u=q.front();
q.pop();//队首出队
inq[u]=false;//出队后即不在队列中
//遍历u的所有邻接边
for(unsigned i=0;i<Adj[u].size();i++)
{
int v=Adj[u][i].v;
int w=Adj[u][i].w;
if(d[u]+w<d[v])//松弛操作
{
d[v]=d[u]+w;
if(!inq[v])// 如果此时v不在队列中，可以入队
{
q.push(v);
inq[v]=true;
num[v]++;
if(num[v]>=n)return false;// 当该点的入队次数大于顶点数时，说明存在可达负环，需要退出算法
}
}
}
}
return true;
}
int main()
{
cin>>n>>p>>c;
for(int i=1;i<=n;i++)
{
cin>>cow[i];
}
int x,y,dis;
for(int i=1;i<=c;i++)
{
cin>>x>>y>>dis;
Adj[x].push_back(Node(y,dis));// 点x的邻接边有y
Adj[y].push_back(Node(x,dis));
}
int minDis=INF;
for(int i=1;i<=p;i++)
{
spfa(i);//枚举每个牧场，作为当前源点
int total=0;// 在当前源点下，所有奶牛行走的最小距离
for(int j=1;j<=n;j++)
{
total+=d[cow[j]];//累加每个奶牛的行走距离
}
if(total<minDis)
{
minDis=total;//每枚举一个源点，更新最小距离
}
}
cout<<minDis;
return 0;
}5、信使--Floyd
【题目描述】 战争时期，前线有n个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。指挥部设在第一个哨所。当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。直至所有n个哨所全部接到命令后，送信才算成功。因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他k个哨所有通信联系的话，这个哨所内至少会配备k个信使）。
现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。
【输入】 第1行有两个整数n和m，中间用1个空格隔开，分别表示有n个哨所和m条通信线路,且1≤n≤100。
第2至m+1行：每行三个整数i、j、k，中间用1个空格隔开，表示第i个和第j个哨所之间存在通信线路，且这条线路要花费k天。
【输出】 一个整数，表示完成整个送信过程的最短时间。如果不是所有的哨所都能收到信，就输出-1。
【输入样例】 4 4 1 2 4 2 3 7 2 4 1 3 4 6 【输出样例】 11
#include<iostream>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int INF=0x7fffffff;
const int N=105;
int dis[N][N];
int main()
{
int n,m,x,y,d;
cin>>n>>m;
fill(dis[0],dis[0]+N*N,INF);//初始化用fill
for(int i=1;i<=m;i++)
{
cin>>x>>y>>d;
dis[x][y]=dis[y][x]=d;//无向图
}
for(int k=1;k<=n;k++)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(i!=j&&i!=k&&j!=k)
{
if(dis[i][k]<INF&&dis[k][j]<INF)//判断是否可以优化
{
if(dis[i][k]+dis[k][j]<dis[i][j])
{
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
}
}
int day=-10000;// 最短时间就是指挥所到其他的一个哨所的最大距离
for(int i=1;i<=n;i++)
{
if(dis[1][i]!=INF&&dis[1][i]>day)
{
day=dis[1][i];
}
}
if(day<0)
{
cout<<-1;
}else
{
cout<<day;
}
return 0;
}