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

鄰接矩陣形式

#include <cstdio>
#include<string.h>
#include <algorithm>
using namespace std;
int graph[210][210];//直接連邊距離
int dis[210];//源點到已知最短路徑的距離
bool vis[210];
int src,ed,n,m;
const int INF=0x3f3f3f3f;
void init()
{
    memset(vis,0,sizeof(vis));
    memset(graph,INF,sizeof(graph));
    for(int i=0;i<n;i++)
        graph[i][i]=0;
}
void dijkstra()
{
    vis[src]=1;
    dis[src]=0;
    for(int i=0;i<n;i++)
        dis[i]=graph[src][i];
    for(int i=1;i<=n-1;i++)
    {
        int k=-1;
        for(int j=0;j<n;j++)
        {
            if(!vis[j]&&((k==-1)||(dis[k]>dis[j])))
               k=j;
        }
        if(k==-1) break;
        vis[k]=1;
        for(int j=0;j<n;j++)
        {
            if(!vis[j]&&(dis[j]>dis[k]+graph[k][j]))
            {
                dis[j]=dis[k]+graph[k][j];
            }
        }

    }
    if(dis[ed]==INF) printf("-1\n");
    else printf("%d\n",dis[ed]);
}
int main()
{
     int u,v,val;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            if(graph[u][v]>val)
            {
                graph[u][v]=val;
                graph[v][u]=val;
            }
        }
        scanf("%d%d",&src,&ed);
        dijkstra();
        //printf("%d\n",INF);

    }
}

前向星+優(yōu)先隊列

#include <cstdio>
#include<string.h>
#include <algorithm>
#include<queue>
#include<vector>
#include<functional>
using namespace std;
typedef pair<int,int> Pair;
const int INF=0x3f3f3f3f;
struct Node
{
    int to,next,w;
}Edge[2010],tmp;
int cnt,head[210],dis[210],src,ed,n,m;
void addEdge(int u,int v,int val)
{
    Edge[cnt].to=v;
    Edge[cnt].w=val;
    Edge[cnt].next=head[u];
    head[u]=cnt++;
}
void init()
{
    memset(head,-1,sizeof(head));
    memset(dis,INF,sizeof(dis));
    cnt=0;
}
void dijkstra()
{
    priority_queue< Pair,vector<Pair>,greater<Pair> > q;
    Pair s;
    s.first=0;
    s.second=src;
    dis[src]=0;
    q.push(s);
    while(!q.empty())
    {
        Pair curr=q.top();
        q.pop();
        int v=curr.second;
        int val=curr.first;
        if(dis[v]<val) continue;
//dis[v]<v.val說明在其他地方對某條u->v邊進行了松弛,才導致現(xiàn)在的dis[v]<val;
//然后v節(jié)點又一次入隊(假設為v*),
//因為v*的val比v的val小,所以肯定是v*先出隊列然后對v*的所有出邊已經(jīng)進行了松弛,
//所以現(xiàn)在的v節(jié)點已經(jīng)沒有必要對它的出邊松弛
        for(int i=head[v];~i;i=Edge[i].next)
        {
            tmp=Edge[i];
            if(dis[tmp.to]>dis[v]+tmp.w)
            {
                dis[tmp.to]=dis[v]+tmp.w;
                q.push(Pair(dis[tmp.to],tmp.to));
            }
        }
    }
    if(dis[ed]==INF) printf("-1\n");
    else printf("%d\n",dis[ed]);
}
int main()
{
     int u,v,val;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        scanf("%d%d",&src,&ed);
        dijkstra();
    }
}