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

DJ

#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#define N 1000001using namespace std;int map[101][101];int n,m;int v[101],dis[101];void D(){    memset(v,0,sizeof(v));    for(int i=1;i<=n;i++)        dis[i]=map[1][i];    dis[1]=0;    v[1]=1;    int min,k;    for(int i=1;i<n;i++)    {        min=N;        for(int j=1;j<=n;j++)        {            if(!v[j]&&min>dis[j])            {                min=dis[j];                k=j;            }        }        v[k]=1;        for(int j=1;j<=n;j++)        {            if(!v[j]&&map[k][j]+dis[k]<dis[j])            {                dis[j]=map[k][j]+dis[k];            }        }    }    printf("%d\n",dis[n]);}int main(){    int x,y,z;    while(scanf("%d%d",&n,&m)!=EOF)    {        if(n==0&&m==0) break;        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                map[i][j]=N;                map[j][i]=N;            }            map[i][i]=0;        }        while(m--)        {            scanf("%d%d%d",&x,&y,&z);            if(map[x][y]>z)            {                map[x][y]=z;                map[y][x]=z;            }        }        D();    }    return 0;}
BE

#include <string.h>#include <stdio.h>#include <stdlib.h>#define N 1000001int n,m,flag,t;struct node{    int x,y,w;}edge[20002];int dis[101];void add(int x,int y,int w){    edge[t].x=x;    edge[t].y=y;    edge[t++].w=w;}void B(){    for(int i=1;i<=n;i++)        dis[i]=N;    dis[1]=0;    for(int i=1;i<n;i++)    {        flag=0;        for(int j=0;j<t;j++)        {            if(edge[j].w+dis[edge[j].x]<dis[edge[j].y])            {                   dis[edge[j].y]=dis[edge[j].x]+edge[j].w;                   flag=1;            }        }        if(flag==0) break;    }    printf("%d\n",dis[n]);}int main(){    int x,y,z;    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))    {        t=0;        while(m--)        {            scanf("%d%d%d",&x,&y,&z);            add(x,y,z);            add(y,x,z);        }        B();    }    return 0;}
F

#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>#define N 1000001using namespace std;int map[101][101];int n,m;void F(){    for(int k=1;k<=n;k++)    {        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                if(map[i][k]+map[k][j]<map[i][j])                    map[i][j]=map[i][k]+map[k][j];            }        }    }}int main(){    int x,y,z;    while(scanf("%d%d",&n,&m)!=EOF)    {        if(n==0&&m==0) break;        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                map[i][j]=N;                map[j][i]=N;            }            map[i][i]=0;        }        while(m--)        {            scanf("%d%d%d",&x,&y,&z);            if(map[x][y]>z)            {                map[x][y]=z;                map[y][x]=z;            }        }        F();        printf("%d\n",map[1][n]);    }    return 0;}

 SPFA

#include <stdio.h>#include <string.h>#include <string.h>#define N 1000001int n,m;struct node{    int x,y,z,next;}edge[20004];int head[102];int dis[102];int v[102];int t;void init(){    memset(head,-1,sizeof(head));    t=0;}void add(int x,int y,int z){    edge[t].x=x;    edge[t].y=y;    edge[t].z=z;    edge[t].next=head[x];    head[x]=t++;}int q[20004];void SPFA(){    memset(v,0,sizeof(v));    for(int i=1;i<=n;i++)        dis[i]=N;    dis[1]=0;    int e=0;    int s=0;    int tt;    q[e++]=1;    v[1]=1;    while(s<e)    {        tt=q[s++];        v[tt]=0;//细心        for(int i=head[tt];i!=-1;i=edge[i].next)        {            if(dis[tt]+edge[i].z<dis[edge[i].y])            {                dis[edge[i].y]=dis[tt]+edge[i].z;                if(v[edge[i].y]==0)                {                   // if(dis[edge[i].y]>dis[q[s]])                    q[e++]=edge[i].y;                  //  else q[--s]=edge[i].y;                    v[edge[i].y]=1;                }            }        }    }    printf("%d\n",dis[n]);}int main(){    int x,y,z;    while(scanf("%d%d",&n,&m)!=EOF&&(m||n))    {        init();        while(m--)        {            scanf("%d%d%d",&x,&y,&z);            add(x,y,z);            add(y,x,z);        }        SPFA();    }}