n个点，m条边，给定起点和终点，求单源最短路径。
（一）dijkstra算法：单源最短路径
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 100
#define sf scanf
#define pf printf
using namespace std;
int n,m,x,y,z; //n个城市和m条道路
int mp[maxn][maxn],lowcost[maxn],vis[maxn],pre[maxn];
void dijkstra(int sta,int edd){for(int i=0;i<n;i++) lowcost[i]=mp[sta][i];vis[sta]=1; lowcost[sta]=0;//寻找距离原点最小的点加进集合 （除原点） for(int i=1;i<n;i++){int Min=inf;int v=-1;for(int j=0;j<n;j++){if(!vis[j]&&lowcost[j]<Min){Min=lowcost[j];v=j;}}//如果又一次更新失败退出此次循环 if(Min==inf) {break;}vis[v]=1;//用新加进来的点松弛for(int k=0;k<n;k++){if(!vis[k]&&lowcost[v]+mp[v][k]<lowcost[k]){lowcost[k]=lowcost[v]+mp[v][k];pre[k]=v;}} }
}int main(){sf("%d%d",&n,&m);for(int i=0;i<n;i++){for(int j=0;j<n;j++){mp[i][j]=inf;}mp[i][i]=0;}for(int i=0;i<m;i++){sf("%d%d%d",&x,&y,&z);mp[x][y]=mp[y][x]=z;}dijkstra(0,n-1);if(lowcost[n-1]==inf ) cout<<"-1"<<endl;else cout<<lowcost[n-1]<<endl; //假设打印起点是0，终点是n-1的路径int sta=0,ed=n-1;pre[sta]=-1;vector<int> ve;vector<int>::iterator ite;while(pre[ed]!=-1){ve.push_back(ed);ed=pre[ed];} reverse(ve.begin(),ve.end());cout<<sta<<" ";for(ite=ve.begin();ite!=ve.end();++ite){cout<<*ite;if(ite!=ve.end()) cout<<" ";else cout<<endl;}return 0;
}（二）floyed：多源最短路径
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 100
#define sf scanf
#define pf printf
using namespace std;
int n,m,x,y,z; //n个城市和m条道路
int mp[maxn][maxn],lowcost[maxn],vis[maxn],pre[maxn],flag=false;//k是中间结点,i是起点,j是终点
void floyed(int mp[][maxn]){for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(mp[i][j]>mp[i][k]+mp[k][j]){mp[i][j]=mp[i][k]+mp[k][j];}}}}
}
int main(){sf("%d%d",&n,&m);for(int i=0;i<n;i++){for(int j=0;j<n;j++){mp[i][j]=inf;}mp[i][i]=0;}for(int i=0;i<m;i++){sf("%d%d%d",&x,&y,&z);mp[x][y]=mp[y][x]=z;}floyed(mp);//可以判断是否存在负环for(int i=0;i<n;i++){if(mp[i][i]<0){flag=true;}} if(flag) cout<<"存在负环"<<endl;else cout<<"不存在负环"<<endl;
// cout<<mp[0][n-1]<<endl; return 0;
}