Floyd && Dijkstra +邻接表 +链式前向星（真题讲解来源：城市路）

1381：城市路(Dijkstra)

时间限制: 1000 ms 内存限制: 65536 KB
提交数: 4066 通过数: 1163

【题目描述】

罗老师被邀请参加一个舞会，是在城市n，而罗老师当前所处的城市为1,附近还有很多城市2~n-1，有些城市之间没有直接相连的路，有些城市之间有直接相连的路，这些路都是双向的，当然也可能有多条。

现在给出直接相邻城市的路长度，罗老师想知道从城市1到城市n，最短多少距离。

【输入】

输入n, m，表示n个城市和m条路;

接下来m行，每行a b c，表示城市a与城市b有长度为c的路。

【输出】

输出1到n的最短路。如果1到达不了n，就输出-1。

【输入样例】

【输出样例】

【提示】

【数据规模和约定】

1≤n≤2000

1≤m≤10000

0≤c≤10000

【来源】

Floyd：（被省略了。。。。）

Dijkstra：

#include<bits/stdc++.h>

using namespace std;

int g[][];

int n,m;

int dis[];

bool used[];

int main(){

    memset(g,0x3f,sizeof(g));

    cin>>n>>m;

    for(int i=;i<=m;++i){

        int a,b,c;

        scanf("%d%d%d",&a,&b,&c);

        g[a][b]=min(g[a][b],c);

        g[b][a]=min(g[b][a],c);

    }

    memset(dis,0x3f,sizeof(dis));

    dis[]=;

    for(int i=;i<=n;++i){

        int minn=0x3f3f3f3f,minn_j=;

        for(int j=;j<=n;++j){

            if(used[j]==false&&dis[j]<minn){

                minn=dis[j];

                minn_j=j;

            }

        }

        if(minn_j==)

            break;

        used[minn_j]=true;

        for(int j=;j<=n;j++)

            if(used[j]==false)

                dis[j]=min(dis[j],dis[minn_j]+g[minn_j][j]);

    }

    if(dis[n]==0x3f3f3f3f)

    cout<<-;

    else

    cout<<dis[n];

}

+领接表：

#include<bits/stdc++.h>

using namespace std;

struct node{

    int to,val;

};

vector<node> edge[];

int dis[];

bool used[];

int main(){

    int n,m;

    cin>>n>>m;

    int a,b,c;

    for(int i=;i<=m;i++){

        cin>>a>>b>>c;

        node t;

        t.to=b;t.val=c;

        edge[a].push_back(t);

        t.to=a;t.val=c;

        edge[b].push_back(t);

    }

    memset(dis,0x3f,sizeof(dis));

    dis[]=;

    for(int i=;i<=n;i++){

         int minn=0x3f3f3f3f,minn_j=;

        for(int j=;j<=n;j++){

            if(used[j]==false&&dis[j]<minn){

                minn=dis[j];

                minn_j=j;

            }

        }

        if(minn_j==)

            break;

        used[minn_j]=true;

        int from=minn_j;

        for(int j=;j<edge[from].size();j++){

            int to=edge[from][j].to;

            int val=edge[from][j].val;

            dis[to]=min(dis[to],dis[from]+val);

        }

    }

    if(dis[n]==0x3f3f3f3f)

        cout<<-;

    else

        cout<<dis[n];

    return ;

}

+链式前向星：

#include<bits/stdc++.h>

using namespace std;

struct node

{

    int to,val,next;

};

node edge[];

int dis[];

bool used[];

int head[];

int num=;

void add_edge(int from,int to,int val)

{

    num++;

    edge[num].to=to;

    edge[num].val=val;

    edge[num].next=head[from];

    head[from]=num;

}

int main()

{

    int n,m;

    cin>>n>>m;

    int a,b,c;

    for(int i=;i<=m;i++)

    {

        cin>>a>>b>>c;

        add_edge(a,b,c);

        add_edge(b,a,c);

    }

    memset(dis,0x3f,sizeof(dis));

    memset(used,false,sizeof(used));

    dis[]=;

    for(int i=;i<=n;i++)

    {

        int minn=0x3f3f3f3f,minn_j=;

        for(int j=;j<=n;j++)

        {

            if(used[j]==false && dis[j]<minn)

            {

                minn=dis[j];

                minn_j=j;

            }

        }

        if(minn_j==)

            break;

        used[minn_j]=true;

        int from=minn_j;

        for(int j=head[from];j!=;j=edge[j].next)

        {

            int to=edge[j].to;

            int val=edge[j].val;

            dis[to]=min(dis[to],dis[from]+val);

        }

    }

    if(dis[n]==0x3f3f3f3f)

        cout<<-;

    else

        cout<<dis[n];

    return ;

}

巴特西