最短路基础

http://acm.hdu.edu.cn/showproblem.php?pid=2544

Dijkstra邻接链表（适用于边少，顶点多）：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0xfffffff
#define N 1100
#include<vector>
using namespace std;

struct node
{
    int e,w;
};

int n,m,vis[N],dist[N];
vector<node>G[N];

void Dij(int Start,int End)
{
    int i,j,Min,index;
    vis[Start]=1;
    dist[Start]=0;

    node p;
    for(i=1; i<=n; i++)
    {
        Min=INF;
        index=Start;
        for(j=1; j<=n; j++)
            if(vis[j]==0&&Min>dist[j])
                Min=dist[j],index=j;
        vis[index]=1;
        int len=G[index].size();
        for(j=0; j<len; j++)
        {
            p=G[index][j];
            if(vis[p.e]==0&&dist[p.e]>dist[index]+p.w)
                dist[p.e]=dist[index]+p.w;
        }
    }

}

int main()
{
    int i,a,b,c;
    node p;
    while(scanf("%d%d",&n,&m),m+n)
    {
        for(i=0; i<N; i++)
        {
            dist[i]=INF;
            vis[i]=0;
            G[i].clear();
        }
        for(i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            p.e=b;
            p.w=c;
            G[a].push_back(p);
            p.e=a;
            G[b].push_back(p);
        }
        Dij(1,n);
        printf("%d
",dist[n]);
    }
    return 0;
}

Dijkstra链接矩阵（适用于变多，顶点少）：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<string.h>
using namespace std;
#define INF 0xfffffff
#define N 1100
int n,m,maps[N][N],dist[N],vis[N];//dist[i]表示从起点到i的最短距离；
void Dij(int Star ,int End)
{
    int i,j,index,Min;
    dist[Star]=0;
    vis[Star]=1;
    index=Star;
    for(i=1;i<=n;i++)
    {
        Min=INF;
        for(j=1;j<=n;j++)
        {
            if(Min>dist[j]&&vis[j]==0)
            {
                Min=dist[j];
                index=j;
            }
        }
        vis[index]=1;
        for(j=1;j<=n;j++)
        {
            if(vis[j]==0&&dist[j]>dist[index]+maps[index][j])
                dist[j]=dist[index]+maps[index][j];
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m),m+n)
    {
        int i,j,a,b,c;
        for(i=0;i<N;i++)
        {
            for(j=0;j<N;j++)
            {
                maps[i][j]=INF;
            }
            vis[i]=0;
            dist[i]=INF;
        }//初始化;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            maps[a][b]=min(maps[a][b],c);
            maps[b][a]=maps[a][b];
        }
        Dij(1,n);
        printf("%d
",dist[n]);
    }
    return 0;
}

Floyd：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define INF 0xfffffff
#define N 1100
using namespace std;
int n,m;
int maps[N][N];
void Floyd()
{
    int i,j,k;
    for(k=1; k<=n; k++)
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
                maps[i][j]=min(maps[i][j],maps[i][k]+maps[k][j]);
        }
}
void Init()
{
    int i,j;
    for(i=0; i<=n; i++)
        for(j=0; j<=n; j++)
            if(i==j)
                maps[i][j]=0;
            else
                maps[i][j]=INF;
}
int main()
{
    int i,a,b,c;
    while(scanf("%d%d",&n,&m),m+n)
    {
        Init();
        for(i=0; i<m; i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            maps[a][b]=maps[b][a]=c;
        }
        Floyd();
        printf("%d
",maps[1][n]);
    }
    return 0;
}

 spfa(适用于点多或者有负环的情况):

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define INF 0xfffffff
#define N 1010
using namespace std;
int Head[N], cnt, dist[N], n, vis[N];
struct Edge
{
    int v, w, next;
} e[N*2];
void Add(int u, int v, int w)
{
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].next=Head[u];
    Head[u]=cnt++;
}
int spfa(int s)
{
    queue<int>Q;
    int u, v;
    memset(vis, 0, sizeof(vis));
    dist[s]=0;
    vis[s]=1;
    Q.push(s);
    while(Q.size())
    {
        u=Q.front();
        Q.pop();
        vis[u]=0;
        for(int i=Head[u]; i!=-1; i=e[i].next)
        {
            v=e[i].v;
            if(dist[v]>dist[u]+e[i].w)
            {
                dist[v]=dist[u]+e[i].w;
                if(!vis[v])
                {
                    vis[v]=1;
                    Q.push(v);
                }
            }
        }
    }
    return dist[n];
}
int main()
{
    int m, a, b, c;
    while(scanf("%d%d", &m, &n)!=EOF)
    {
        memset(Head, -1, sizeof(Head));
        for(int i=0; i<=n; i++)
            dist[i] = INF;
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d", &a, &b, &c);
            Add(a, b, c);
            Add(b, a, c);
        }
        int ans = spfa(1);
        printf("%d
", ans);
    }
    return 0;
}