无向图邻接表如何建，求指点！ HDU 2544 最短路（Dijkstra、结题报告 精简版！）

无向图邻接表怎么建，求指点！！ HDU 2544 最短路（Dijkstra、结题报告 精简版！）

转载请注明出自cxb569262726：http://write.blog.csdn.net/postedit

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=2544

代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 105
#define INF 100000
using namespace std;
int map[MAXN][MAXN],used[105],d[105];
int main()
{
    int i,j,n,m,t,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF && (n||m))
    {
        for(i=0;i<MAXN;i++)
            for(j=0;j<MAXN;j++) map[i][j]=INF;
        memset(used,0,sizeof(used));
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(c<map[a][b]) map[a][b]=map[b][a]=c;
        }
        for(i=1;i<=n;i++) d[i]=map[1][i];
        used[1]=1;
        for(i=1;i<n;i++)
        {
            int k,mini=INF;
            for(j=1;j<=n;j++) if(!used[j] && d[j]<mini) mini=d[k=j];
            used[k]=1;
            for(j=1;j<=n;j++) if(!used[j] && d[j]>d[k]+map[k][j]) d[j]=d[k]+map[k][j];
        }
        printf("%d\n",d[n]);
    }
    return 0;
}

PS：今晚本来用邻接表写了这题的，没想到邻接表不好写啊！！ 还花大时间写白书上的刘汝佳式邻接表，我勒个去，那是有向图的，无向图我这菜鸟不会修改。。。

  求高手指教啊，以下代码是wa的：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<vector>
#define MAXN 105
#define INF 100000
using namespace std;
typedef pair<int,int> pii;
int used[MAXN],d[MAXN],u[MAXN],v[MAXN],w[MAXN*2],next[MAXN*2],first[MAXN];
int main()
{
    int i,j,n,m,t,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF && (n||m))
    {
        priority_queue<pii,vector<pii>,greater<pii> > q;
        memset(used,0,sizeof(used));
        memset(first,-1,sizeof(first));
        for(i=0;i<2*m;i+=2)//本来是i++的，无向图我改了 
        {
            scanf("%d%d%d",&u[i],&v[i],&w[i]);
            next[i]=first[u[i]];    first[u[i]]=i;
            next[i+1]=first[v[i+1]];    first[v[i]]=i+1;//多加条边 
            w[i+1]=w[i];v[i+1]=u[i];u[i+1]=v[i];//相应的起点终点权值 
        }
        d[1]=0; for(i=2;i<=n;i++) d[i]=INF;
        q.push(make_pair(d[1],1));
        while(!q.empty())
        {
            pii z=q.top(); q.pop();
            int x=z.second;
            if(used[x]) continue;
            used[x]=1;
            for(i=first[x];i!=-1;i=next[i]) 
                if(d[v[i]]>d[x]+w[i])
                {
                    d[v[i]]=d[x]+w[i];
                    q.push(make_pair(d[v[i]],v[i]));
                }
        }
        printf("%d\n",d[n]);
    }
    return 0;
}

以上代码是数组开小了，还有赋值的时候顺序反了,正确代码：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<vector>
#define MAXN 10005
#define INF 100000000
using namespace std;
typedef pair<int,int> pii;
int used[105],d[105],u[MAXN*2],v[MAXN*2],w[MAXN*2],next[MAXN*2],first[MAXN];
int main()
{
    int i,j,n,m,t,a,b,c;
    while(scanf("%d%d",&n,&m)!=EOF && (n||m))
    {
        priority_queue<pii,vector<pii>,greater<pii> > q;
        memset(used,0,sizeof(used));
        memset(first,-1,sizeof(first));
        for(i=0;i<2*m;i+=2)//本来是i++的，无向图我改了 
        {
            scanf("%d%d%d",&u[i],&v[i],&w[i]);
            next[i]=first[u[i]];    first[u[i]]=i;
            w[i+1]=w[i];v[i+1]=u[i];u[i+1]=v[i];//相应的起点终点权值 
            next[i+1]=first[u[i+1]];    first[v[i]]=i+1;//多加条边 
        }
        d[1]=0; for(i=2;i<=n;i++) d[i]=INF;
        q.push(make_pair(d[1],1));
        while(!q.empty())
        {
            pii z=q.top(); q.pop();
            int x=z.second;
            if(used[x]) continue;
            used[x]=1;
            for(i=first[x];i!=-1;i=next[i]) 
                if(d[v[i]]>d[x]+w[i])
                {
                    d[v[i]]=d[x]+w[i];
                    q.push(make_pair(d[v[i]],v[i]));
                }
        }
        printf("%d\n",d[n]);
    }
    return 0;
}

1楼cxb569262726昨天 01:43

明天要早起。。。睡觉了！