HDU-2544: 最短路（dij+优先队列+邻接表 | 邻接矩阵）

最短路

Description

在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？

Input

输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

Output

对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间

Sample Input

2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output

3
2

邻接矩阵

将两点之间的信息保存在邻接矩阵中，使用dijkstra算法寻找最短路。dis数组存入的是从起点到某点的最短距离，最开始初始化要最大，因此memset(dis,127,sizeof(dis));在dij函数中每找到短的一条路径就根据这一路径更新其他路径。

• 输入：由于是无向图，因此要存两个方向

while(m--)
{
    scanf("%d%d%d",&a,&b,&c);
    if(c<ma[a][b])
    {
        ma[a][b]=c;
        ma[b][a]=c; //双向
    }
}

• dijkstra：从起点开始，标记它，并且设其他点都未标记。检验所有已标记的点到与它直接相连的未标记的点的距离，取最小值。再选取下一个未标记的点中dis最小的点，重复操作。

void dij()
{
    int i,j,x,pos;
    for(i=1;i<=n;i++)
        dis[i]=ma[1][i]; //从1到i点的距离
    vis[1]=1; //标记起点
    for(i=1;i<n;i++) //n个点，也就是该题中的路口
    {
        x=INF;
        for(j=1;j<=n;j++) 
        {
            if(vis[j]==0&&dis[j]<x) //没有经过某位置
            {
                x=dis[j]; //从所有没有标记的点中，选择一个dis最小的
                pos=j;
            }
        }
        vis[pos]=1; //标记这个最小的点
        for(j=1;j<=n;j++) //并且用这个最小的点更新其他路径
            if(vis[j]==0&&dis[j]>dis[pos]+ma[pos][j]) //如果经过pos点再到j的距离比原来的更短，更新
                dis[j]=dis[pos]+ma[pos][j];
    }
}

• 完整代码：

#include<stdio.h>
#include<string.h>
#define INF 1e9
int ma[111][111],m,n,dis[111],vis[111];
void dij()
{
    int i,j,x,pos;
    for(i=1;i<=n;i++)
        dis[i]=ma[1][i]; //从1到i点的距离
    vis[1]=1;
    for(i=1;i<n;i++)
    {
        x=INF;
        for(j=1;j<=n;j++)
        {
            if(vis[j]==0&&dis[j]<x)
            {
                x=dis[j]; 
                pos=j;
            }
        }
        vis[pos]=1;
        for(j=1;j<=n;j++)
            if(vis[j]==0&&dis[j]>dis[pos]+ma[pos][j]) //如果经过pos点再到j的距离比原来的更短，更新
                dis[j]=dis[pos]+ma[pos][j];
    }
}
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&m),n+m)
    {
        memset(ma,127,sizeof(ma));
        memset(vis,0,sizeof(vis));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            if(c<ma[a][b])
            {
                ma[a][b]=c;
                ma[b][a]=c; //双向
            }
        }
        dij();
        printf("%d\n",dis[n]);
    }
    return 0;
}

邻接表

邻接表可以用于无向图，也可以用于有向图，用数组实现链表，比vector的时间复杂度更低一点。

• 建立邻接表：每次的插入是插入到链表的首部。【这里搞不太清楚】
  同样，由于是无向图，要添加两个方向。

void add(int st,int en,int val)
{
    a[num].en=en;
    a[num].val=val;
    a[num].next=pos[st]; 
    pos[st]=num;
    num++;
}

• dijkstra：

void dij()
{
    int i,j,x,id;
    dis[1]=0; //起点
    for(i=1;i<=n;i++)
    {
        x=INF;
        for(j=1;j<=n;j++)
        {
            if(vis[j]==0&&dis[j]<x) //没有经过并且距离更短，就使用这个点
            {
                x=dis[j]; //从所有没有标记的点中，选择一个dis最小的
                id=j; 
            }
        }
        vis[id]=1; //使用后标记
        for(j=pos[id];j!=-1;j=a[j].next) //与这个点相连的其他点
        {
            if(dis[a[j].en]>dis[id]+a[j].val)             //如果原来到这点的距离比现在的更长，用现在的距离更新
                dis[a[j].en]=dis[id]+a[j].val;
        }
    }
}

• 完整代码：

#include<stdio.h>
#include<string.h>
#define INF 1e9
struct node
{
    int en,val,next;
}a[100005];
int vis[111],pos[111],dis[111],num,n,m;
void add(int st,int en,int val)
{
    a[num].en=en;
    a[num].val=val;
    a[num].next=pos[st]; //好像是加到前面的意思……再理解= =不行就记住
    pos[st]=num;
    num++;
}
void dij()
{
    int i,j,x,id;
    dis[1]=0; //起点
    for(i=1;i<=n;i++)
    {
        x=INF;
        for(j=1;j<=n;j++)
        {
            if(vis[j]==0&&dis[j]<x) //没有经过并且距离更短，就使用这个点
            {
                x=dis[j];
                id=j; 
            }
        }
        vis[id]=1; //使用后标记
        for(j=pos[id];j!=-1;j=a[j].next) //这里也不是很清楚
        {
            if(dis[a[j].en]>dis[id]+a[j].val) //如果原来到这点的距离比现在的更长，用现在的距离更新
                dis[a[j].en]=dis[id]+a[j].val;
        }
    }
}
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&m),n+m)
    {
        memset(vis,0,sizeof(vis));
        memset(pos,-1,sizeof(pos));
        memset(dis,127,sizeof(dis)); //距离初始化最大值
        num=0;
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c); //无向图，添加两个方向
        }
        dij();
        printf("%d\n",dis[n]); //到n的最短时间
    }
    return 0;
}

邻接表+优先队列优化

如果不用优先队列优化，每次找到最短距离需要二重循环，复杂度为$n^2$，使用优先队列，复杂度为$nlog_2n$。
其实这个并不是很懂……都是照着模板打的

• 结构体：除了node1结构体外，还有一个node2结构体，存放的应该大概可能也许是到达的某点和路径的长度（或者是时间等）。因为要使用优先队列，所以要在该结构体中重载小于符号。

struct node2
{
    int id,val; //id是尾位置吧大概……
    node2(int id1=0,int val1=0) //构造函数
    {
        id=id1;val=val1;
    }
    friend bool operator <(node2 x,node2 y) //重载＜符号
    {
        return x.val>y.val; 
    }
};

• 建立邻接表：和不用优先队列优化的一样，此处省略。懒得粘

• dijkstra+优先队列：

void dij()
{
    dis[1]=0; //起点
    node2 now;
    priority_queue<node2>q;
    q.push(node2(1,0)); //因为前面有构造函数，所以此处可以直接写node2(1,0)
    //1表示的现在的点，0是距离
    while(!q.empty())
    {
        int i;
        now=q.top();
        q.pop();
        if(vis[now.id]==1) continue; 
        vis[now.id]=1; //选取没有标记的点放入另一个集合中，然后标记它
        for(i=pos[now.id];i!=-1;i=a[i].next) //与上一个相同，找它相连的其他未标记的点
        {
            if(vis[a[i].en]==0&&dis[a[i].en]>dis[now.id]+a[i].val) //松弛操作
            {
                dis[a[i].en]=dis[now.id]+a[i].val;
                q.push(node2(a[i].en,dis[a[i].en]));
            }
        }
    }
}

• 代码：

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
int n,m,vis[111],num,pos[111],dis[111];
struct node1
{
    int en,val,next;
}a[100005];
struct node2
{
    int id,val; //id是位置
    node2(int id1=0,int val1=0) //构造函数
    {
        id=id1;val=val1;
    }
    friend bool operator <(node2 x,node2 y) //重载＜符号
    {
        return x.val>y.val; 
    }
};
void add(int st,int en,int val)
{
    a[num].en=en;
    a[num].val=val;
    a[num].next=pos[st];
    pos[st]=num;
    num++;
}
void dij()
{
    dis[1]=0;
    node2 now;
    priority_queue<node2>q;
    q.push(node2(1,0));
    while(!q.empty())
    {
        int i;
        now=q.top();
        q.pop();
        if(vis[now.id]==1) continue; //该点走过
        vis[now.id]=1;
        for(i=pos[now.id];i!=-1;i=a[i].next)
        {
            if(dis[a[i].en]>dis[now.id]+a[i].val)
            {
                dis[a[i].en]=dis[now.id]+a[i].val;
                q.push(node2(a[i].en,dis[a[i].en]));
            }
        }
    }
}
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&m),n+m)
    {
        num=0;
        memset(dis,127,sizeof(dis));
        memset(vis,0,sizeof(vis));
        memset(pos,-1,sizeof(pos));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        dij();
        printf("%d\n",dis[n]);
    }
    return 0;
}

vector+优先队列优化

vector是一种容器，其实就相当于数组，里面自带有许多函数（但是我不会用 而且觉得自己没有学过C++更不会STL），比通过数组实现的邻接矩阵更容易理解，但是貌似调用vector里面的函数时间复杂度更高一点。

• 建立邻接矩阵： 首先要声明一个vector，vector<node> v[11111];，vector的编号（0-11111）表示起点，node中存终点和到终点的时间

while(m--)
{
    scanf("%d%d%d",&a,&b,&c);
    v[a].push_back(node(b,c));
    v[b].push_back(node(a,c));
    //起点a，终点b，时间c存入vector，起点b终点a时间c存入
}

• 结构体：

struct node
{
    int en,val; //en是目标点，val是到该点的时间
    node(int en1=0,int val1=0) //构造函数，然后就可以在下面直接写node(a,b)
    {
        en=en1;val=val1;
    }
    friend bool operator <(node x,node y) //重载＜符号
    {
        return x.val>y.val;
    }
};

• dijkstra+优先队列：

void dij()
{
    dis[1]=0;//起点
    priority_queue<node>q; //优先队列优化，每次弹出时间最短的
    q.push(node(1,dis[1])); //压入起点和dis
    while(!q.empty())
    {
        node now,next;
        now=q.top();
        q.pop();
        if(vis[now.en]==1) 
            continue;
        vis[now.en]=1; //选取没有标记的点放入另一个集合中，然后标记它
        for(int i=0;i<v[now.en].size();i++)
        {
            next=v[now.en][i]; //！！开了vector[11111]貌似相当于一个二维的数组，但是不会用…然后去看了别人怎么写的
            if(dis[next.en]>now.val+next.val) //松弛操作
            {
                dis[next.en]=now.val+next.val;
                q.push(node(next.en,dis[next.en]));
            }
        }
    }
}

• 完整代码：

#include<stdio.h>
#include<queue>
#include<string.h>
#include<vector>
#define INF 1e9
using namespace std;
int n,m,vis[111],dis[111];
struct node
{
    int en,val; //id是位置
    node(int en1=0,int val1=0) //构造函数= =然后就可以在下面直接写node(a,b)
    {
        en=en1;val=val1;
    }
    friend bool operator <(node x,node y) //重载＜
    {
        return x.val>y.val;
    }
};
vector<node> v[11111]; //vector的编号表示起点，node中存终点和到终点的时间
void dij()
{
    dis[1]=0;//起点
    priority_queue<node>q; //优先队列优化，每次弹出时间最短的
    q.push(node(1,dis[1]));
    while(!q.empty())
    {
        node now,next;
        now=q.top();
        q.pop();
        if(vis[now.en]==1) 
            continue;
        vis[now.en]=1;
        for(int i=0;i<v[now.en].size();i++)
        {
            next=v[now.en][i]; 
            if(dis[next.en]>now.val+next.val)
            {
                dis[next.en]=now.val+next.val;
                q.push(node(next.en,dis[next.en]));
            }
        }
    }
}
int main()
{
    int a,b,c;
    while(scanf("%d%d",&n,&m),n+m)
    {
        memset(dis,127,sizeof(dis));
        memset(vis,0,sizeof(vis));
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            v[a].push_back(node(b,c));
            v[b].push_back(node(a,c));
            //起点a，终点b，时间c存入vector，起点b终点a时间c存入
        }
        dij();
        printf("%d\n",dis[n]);
        for(int i=0;i<11111;i++)
            v[i].clear();
    }
    return 0;
}