HDU - 2544 最短路（Flody，Dijkstra，SPFA）

HDU - 2544 最短路

SPFA（邻接表+队列）

#include<bits/stdc++.h>
using namespace std;
const int INF=1e6;
const int N=110;
struct edge
{
    int from,to,w;edge (int a,int b,int c){
     from=a;to=b;w=c;} 
};
vector<edge>e[N];
int n,m;
int dis[N];
bool inq[N];
//int neg[N];//判断负环 
int pre[N];
void spfa(int s)
{
    //memset(neg,0,sizeof neg);//判断负环 //neg[s]=1;//判断负环 for(int i=1;i<=n;i++) {
     dis[i]=INF;inq[i]=false;}dis[s]=0;queue<int>q;q.push(s);inq[s]=true;while(!q.empty()) {
    int u=q.front();q.pop();inq[u] = false;for(int i=0;i<e[u].size();i++){
    int v=e[u][i].to,w=e[u][i].w;if(dis[u]+w<dis[v]){
    dis[v]=dis[u]+w;pre[v]=u;if(!inq[v]) {
    inq[v] = true;q.push(v);//neg[v]++;//判断负环 
// if(neg[v]>n) return 1;//判断负环 }}}}
}
int main()
{
    while(~scanf("%d%d",&n,&m)){
    if(n==0&&m==0) break;for(int i=1;i<=n;i++) e[i].clear();while(m--){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);e[a].push_back(edge(a,b,c));e[b].push_back(edge(b,a,c));}spfa(1);printf("%d\n",dis[n]);}return 0;
} 

Dijkstra（邻接矩阵）

#include<iostream>
#include<cstring>
using namespace std;
const int INF = 1e9;
int n,m;
int e[110][110],dis[110],vis[110];
void dijkstra(int s)
{
    memset(vis,0,sizeof vis);for(int i=1;i<=n;i++) dis[i]=e[s][i];dis[s]=0;for(int i=1;i<=n-1;i++){
    int minn=INF,u;for(int j=1;j<=n;j++)if(!vis[j]&&minn>dis[j]){
    minn=dis[j];u=j;} vis[u]=1;for(int j=1;j<=n;j++){
    if(!vis[j]&&dis[j]>dis[u]+e[u][j]) dis[j]=dis[u]+e[u][j];}}
}
int main()
{
    while(cin>>n>>m&&n+m){
    for(int i=0;i<=n;i++)	for(int j=0;j<=n;j++)if(i==j) e[i][j]=0;else e[i][j]=INF;while(m--){
    int a,b,c;cin>>a>>b>>c;if(c<e[a][b])e[a][b]=e[b][a]=c; }dijkstra(1);cout<<dis[n]<<endl;} return 0;
}

Flody

#include<iostream>
using namespace std;
int e[110][110];
int n,m;
int main(void)
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);while(cin>>n>>m){
    if(n==0&&m==0) return 0;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){
    if(i==j) e[i][j]=0;else e[i][j]=9999999;}while(m--){
    int a,b,c;cin>>a>>b>>c;e[a][b]=e[b][a]=c;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)if(e[i][k]!=9999999) for(int j=1;j<=n;j++)e[i][j]=min(e[i][j],e[i][k]+e[k][j]);cout<<e[1][n]<<endl; }return 0;
}