最短路径算法（跟新SPFA，Ford）

//以城市路为蓝本介绍算法

1381：城市路(Dijkstra)

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

【题目描述】

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

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

【输入】

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

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

【输出】

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

【输入样例】

5 5

1 2 20

2 3 30

3 4 20

4 5 20

1 5 100

【输出样例】

90

【提示】

【数据规模和约定】

1≤n≤2000

1≤m≤10000

0≤c≤10000

【来源】

No

SPAF：

#include<bits/stdc++.h>

using namespace std;

struct node

{

    int next,to,val;

}edge[];

int h[],num=;

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

{

    num++;

    edge[num].to=to;

    edge[num].val=val;

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

    h[from]=num;

}

int dis[];

bool used[];

int Q[],head,tail;

int main()

{

    int n,m;

    cin>>n>>m;

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

    {

        int x,y,z;

        cin>>x>>y>>z;

        add_edge(x,y,z);

        add_edge(y,x,z);

    }

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

    dis[]=;

    Q[]=;head=;tail=;used[]=true;

    while(head<=tail)

    {

        //1.取出头结点

        int from=Q[head];

        head++;

        used[from]=false;

        //2.拓展新的尾结点

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

        {

            int to=edge[j].to;

            int val=edge[j].val;

            if(dis[to]>dis[from]+val)

            {

                dis[to]=dis[from]+val;

                if(!used[to])

                {

                    tail++;

                    Q[tail]=to;

                    used[to]=true;

                }

            }

        }

    }

    if(dis[n]==0x3f3f3f3f)

        cout<<-;

    else

        cout<<dis[n];        

    return ;

}

Ford:

#include<bits/stdc++.h>

using namespace std;

struct node

{

    int from,to,val;

}edge[];

int num;

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

{

    num++;

    edge[num].from=from;

    edge[num].to=to;

    edge[num].val=val;

}

int dis[];

int main()

{

    int n,m;

    cin>>n>>m;

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

    {

        int x,y,z;

        cin>>x>>y>>z;

        add_edge(x,y,z);

    }

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

    dis[]=;

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

    {

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

        {

            int from=edge[j].from;

            int to=edge[j].to;

            int val=edge[j].val;

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

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

        }

    }

    if(dis[n]==0x3f3f3f3f)

        cout<<-;

    else

        cout<<dis[n];

    return ;

}

//~~可能并不能过。。。。~~

最短路径算法（跟新SPFA，Ford）的相关教程结束。