模板测试题目：http://acm.hdu.edu.cn/showproblem.php?pid=2544
Floyd
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int LL;int n,m;
int a[110][110];
int main()
{while(cin>>n>>m&&n&&m){memset(a,inf,sizeof(a));for(int i=0; i<m; i++){int x,y,z;cin>>x>>y>>z;if(a[x][y]>z)a[x][y]=a[y][x]=z;}for(int k=1; k<=n; k++){for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){if(a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j];}}}cout<<a[1][n]<<endl;}return 0;
}Dijkstra
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int LL;struct A
{int ed,cost;
}tmp;
int n,m;
vector<A> v[110];
int dis[110],vis[110];void Dijkstra(int start)
{memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));dis[start]=0;vis[start]=1;for(int i=0;i<v[start].size();i++){dis[v[start][i].ed]=v[start][i].cost;}for(int l=1;l<n;l++){int mini=inf;int k=0;for(int i=1;i<=n;i++){if(dis[i]<mini&&vis[i]==0){mini=dis[i];k=i;}}vis[k]=1;for(int i=0;i<v[k].size();i++){int u=v[k][i].ed;int r=v[k][i].cost;if(dis[k]+r<dis[u]&&vis[u]==0)dis[u]=dis[k]+r;}}return;
}int main()
{while(cin>>n>>m&&n&&m){for(int i=0;i<=n;i++)v[i].clear();for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;tmp.cost=z;tmp.ed=y;v[x].push_back(tmp);tmp.ed=x;v[y].push_back(tmp);}Dijkstra(1);cout<<dis[n]<<endl;}return 0;
}堆优化Dijkstra（优先队列）
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#define eps 0.0000000001
#define mem(a) memset(a,0,sizeof(a))
#define maxx 1e10
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
#define mod 1000000007const int maxn=100010;struct point
{int loc,cost;bool operator < (const point &c) const{return cost>c.cost;}
};struct edge
{int to,cost;
};
vector <edge> a[maxn];
bool vis[maxn];
int dis[maxn];
int start;
int n,m;
point add(int x,int y)
{point rem;rem.loc=x;rem.cost=y;return rem;
}
void addedge(int u,int v,int w)
{edge tmp;tmp.to=v;tmp.cost=w;a[u].push_back(tmp);tmp.to=u;a[v].push_back(tmp);
}
void dijkstra(int start)
{memset(vis,0,sizeof(vis));memset(dis,inf,sizeof(dis));priority_queue <point> q;dis[start]=0;q.push(add(start,0));point tmp;while (!q.empty()){tmp=q.top();q.pop();int u=tmp.loc;if (vis[u]==1)continue;vis[u]=1;for (int i=0; i<a[u].size(); i++){int x=a[u][i].to;int y=a[u][i].cost;if (vis[x]==0 && dis[x]>dis[u]+y){dis[x]=dis[u]+y;q.push(add(x,dis[x]));}}}return;
}
int main()
{while(cin>>n>>m&&n&&m){for(int i=0;i<10000;i++)a[i].clear();for (int i=1; i<=m; i++){int u,v,w;cin>>u>>v>>w;addedge(u,v,w);}dijkstra(1);cout<<dis[n]<<endl;}return 0;
}
Bellman_Ford
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int LL;struct A
{int x,y,cost;
};
A a[10100];
int dis[110];
int n,m,start=1;void Init()
{memset(dis,inf,sizeof(dis));dis[start]=0;for(int i=1;i<=m;i+=2){cin>>a[i].x>>a[i].y>>a[i].cost;a[i+1].x=a[i].y;a[i+1].y=a[i].x;a[i+1].cost=a[i].cost;if(a[i].x==start)dis[a[i].y]=a[i].cost;if(a[i].y==start)dis[a[i].x]=a[i].cost;}
}
bool Bellman_Ford()
{for(int i=1;i<=n-1;i++){for(int j=1;j<=m;j++){if(dis[a[j].y]>dis[a[j].x]+a[j].cost)dis[a[j].y]=dis[a[j].x]+a[j].cost;}}bool flag=1;for(int i=1;i<=m;i++){if(dis[a[i].y]>dis[a[i].x]+a[i].cost){flag=0;break;}}return flag;
}int main()
{while(cin>>n>>m&&n&&m){m*=2;Init();Bellman_Ford();cout<<dis[n]<<endl;}return 0;
}SPFA
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cstdio>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long int LL;struct A
{int ed,cost;
}tmp;
int n,m;
vector<A> v[110];
int dis[110],vis[110];void SPFA(int start)
{memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));dis[start]=0;vis[start]=1;queue<int> q;q.push(start);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=0;i<v[u].size();i++){int x=v[u][i].ed;int y=v[u][i].cost;if(dis[u]+y<dis[x]){dis[x]=dis[u]+y;if(vis[x]==0){q.push(x);vis[x]=1;}}}}return;
}int main()
{while(cin>>n>>m&&n&&m){for(int i=0;i<=n;i++)v[i].clear();for(int i=0;i<m;i++){int x,y,z;cin>>x>>y>>z;tmp.cost=z;tmp.ed=y;v[x].push_back(tmp);tmp.ed=x;v[y].push_back(tmp);}SPFA(1);cout<<dis[n]<<endl;}return 0;
}