1088: 最短路（SPFA算法 &dij）

48 阅读 0 评论 32 点赞

我是靠谱客的博主冷静雪糕，最近开发中收集的这篇文章主要介绍1088: 最短路（SPFA算法 &dij），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1088: [视频]最短路（模版 SPFA算法元问题 by scy）
时间限制: 1 Sec 内存限制: 128 MB
提交: 630 解决: 236
[提交][状态][讨论版]
题目描述
【题意】
给出一个图，起始点是1，结束点是N，边是双向的。求点1到点N的最短距离。哈哈，这就是标准的最短路径问题。
【输入格式】
第一行为两个整数N（1≤N≤10000）和M（0≤M≤200000）。N表示图中点的数目，M表示图中边的数目。
下来M行，每行三个整数x，y，c表示点x到点y之间存在一条边长度为c。（x≠y,1≤c≤10000）
【输出格式】
输出一行，一个整数，即为点1到点N的最短距离。
如果点1和点N不联通则输出-1。
【样例1输入】
2 1
1 2 3
【样例1输出】
3

【样例2输入】
3 3
1 2 5
2 3 5
3 1 2
【样例2输出】
2

【样例3输入】
6 9
1 2 7
1 3 9
1 5 14
2 3 10
2 4 15
3 4 11
3 5 2
4 6 6
5 6 9
【样例3输出】
20

**当存在负权边时，dijstra算法就不能保证输出正确答案。所以采用SPFA算法。
另外需要说明的是，如果图中不存在负权边，那么dijstra依旧是效率最高的算法。**

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int INF = 1<<29;
int _map[500][500];
int vis[500];
int len[500];
queue <int> que;
int x,y,c,n,m,start,last;
void spfa(int s)
{
    for (int i=0;i<=n;i++)
    {
        vis[i]=0;
        len[i]=INF;
    }
    len[s]=0;
    queue <int > que;
    que.push(s);
    while(!que.empty())
    {
        int num=que.front();
        for (int i=1;i<=n;i++)
        {
            if (len[i]>len[num]+_map[num][i])
            {
                len[i]=len[num]+_map[num][i];
                if (!vis[i])
                {
                    vis[i]=true;
                    que.push(i);
                }
            }
        }
        vis[num]=false;
        que.pop();
    }
}
int main()
{
    cin>>n>>m;
    memset(_map,63,sizeof(_map));
    for (int i=0;i<m;i++)
    {
        cin>>x>>y>>c;
        _map[x][y]=_map[y][x]=c;
    }
    start=1;
    last=n;
    spfa(start);
    cout<<len[last]<<endl;
    return 0;
}

另外此题并不含负权边，所以可以使用dij算法。
另附如下代码：

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair <int ,int> P;
const int INF = 1<<29;
int _map[500][500];
int vis[500];
int len[500];
int x,y,c,n,m,start,last;
void dij(int s)
{
    for (int i=0;i<=n;i++)
    {
        vis[i]=0;
        len[i]=INF;
    }
    len[s]=0;
    priority_queue<P,vector<P> ,greater<P> > que;
    que.push({len[s],s});
    while(!que.empty())
    {
        P temp =que.top();
        que.pop();
        int num=temp.second;
        if (vis[num]) continue;
        vis[num]=1;
        for (int i=1;i<=n;i++)
        {
            if (len[i]>len[num]+_map[num][i])
            {
                len[i]=len[num]+_map[num][i];
                que.push({len[i],i});
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    memset(_map,63,sizeof(_map));
    for (int i=0;i<m;i++)
    {
        cin>>x>>y>>c;
        _map[x][y]=_map[y][x]=c;
    }
    start=1;
    last=n;
    dij(start);
    cout<<len[last]<<endl;
    return 0;
}