来道例题吧：hdu1874
AC代码如下：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
const int maxn=205;
int n,m;
int mp[maxn][maxn];
int main(){
while(cin>>n>>m){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j) mp[i][j]=0;
else mp[i][j]=INF;
}
}
for(int i=1;i<=m;i++){
int x,y,z;cin>>x>>y>>z;
mp[x][y]=min(z,mp[x][y]);
mp[y][x]=min(z,mp[y][x]);
}
int s,t;cin>>s>>t;
//Floyd的写法：
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
}
//止
if(mp[s][t]==INF) cout<<"-1"<<endl;
else cout<<mp[s][t]<<endl;
}
}
这里我解释一下Floyd算法，他是求两个点最短路径的，这里运用了dp的思维。
设起点为s，终点为t，路过的一个点(即搭桥点为k)
核心关键就是dp[s][t]=min(dp[s][t],dp[s][k]+dp[k][t])
这就是状态转移，最后存最小即可