P4779 【模板】单源最短路径（标准版） - 洛谷 | 计算机科学教育新生态

题目背景

2018年7月19日，某位同学在NOI Day 1 T1 归程一题里非常熟练地使用了一个广为人知的算法求最短路。

然后呢？

100 → 60：

Ag → Cu：

最终，他因此没能与理想的大学达成约。

小F衷心祝愿大家不再重蹈覆辙。

以下是根据图片内容生成的格式化文档：

---

题目描述

给定一个n个点，m条有向边的带非负权图，请你计算从s出发，到每个点的距离。
数据保证你能从s出发到任意点。

输入格式

第一行为三个正整数n，m，s。第二行起m行，每行三个非负整数w，vi, wi，表示从uᵢ到vᵢ有一条权值为wᵢ的有向边。

输出格式

输出一行n个空格分隔的非负整数，表示s到每个点的距离。

输入输出样例

输入#1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出#1

0 2 4 3

说明/提示

样例解释请参考数据随机的模板题。

• 1≤n≤1e5
• 1≤m≤2×1e5
• s=1
• 1≤ui​,vi​≤n
• 0≤wi​≤1e9
• 0≤∑wi​≤1e9

本题数据可能会持续更新，但不会重测，望周知。

2018.09.04 数据更新 from @zzq

思路：

spfa算法，超时的。

代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 2e5 * 5 + 5;
ll tot = 0;
ll n, m, s;
struct Edge{
	ll next,to,w;
}e[N];
ll head[N],dis[N]; 
void add(ll u,ll v,ll w)
{
	tot++;
	e[tot].next = head[u];
	e[tot].to = v;
	e[tot].w = w;
	head[u] = tot;
}
void spfa() 
{
    bool vis[N] = {false};  
    queue<ll> q;
    q.push(s);
    vis[s] = true;
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;

    while (!q.empty()) 
	{
        ll pos = q.front();
        q.pop();
        vis[pos] = false;  // 标记为不在队列中

        for (ll u = head[pos]; u != -1; u = e[u].next) 
		{
            ll to = e[u].to;
            ll w = e[u].w;
            // 先判断能否松弛，不管 to 是否在队列中
            if (dis[to] > dis[pos] + w) 
			{
                dis[to] = dis[pos] + w;// 松弛成功后，若 to 不在队列则入队
                if (!vis[to]) 
				{
                    q.push(to);
                    vis[to] = true;
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m >> s;
    for(ll i = 1 ; i <= n ; i++)
    head[i] = -1;
    for(ll i = 1 ; i <= m ; i++)
	{
        ll u,v,w;
        cin >> u >> v >> w;
        add(u,v,w);
    }
    spfa();
    for(ll i = 1 ; i <= n ; i++)
	cout << dis[i] << " "; 
    return 0;
}

思路如下：

dijstra算法

由于数据超过了1e5,所以用邻接表构图即可。
代码如下：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstring>
using namespace std;
typedef long long ll;
const ll N = 2e5 * 5 + 5;
ll tot = 0;
ll n, m, s;
struct Edge 
{
    ll next;
    ll to;
    ll w;
} e[N];
typedef pair<int, int> PII;
ll head[2 * N], dis[2 * N];
bool vis[2 * N];
// 添加边
void add(ll u, ll v, ll w) {
    tot++;
    e[tot].next = head[u];
    e[tot].to = v;
    e[tot].w = w;
    head[u] = tot;
}
// 初始化
void init() {
    memset(dis, 0x3f, sizeof(dis));  // 初始化最短距离为无穷大
    memset(head, -1, sizeof(head));   // 初始化图的头指针
    memset(vis, false, sizeof(vis));  // 初始化所有节点未访问
}
void dijkstra() {
    priority_queue<PII, vector<PII>, greater<PII>> q;  // 优先队列，最小堆,对第一个int排序，也就是d 
    dis[s] = 0;
    q.push({0, s});  
    
    while (!q.empty()) {
        auto k = q.top();  // 取出队首元素
        q.pop();            // 出队
        ll d = k.first, pos = k.second;
        
        if (vis[pos]) continue;  // 如果该节点已经访问过，跳过
        vis[pos] = true;

        // 遍历该节点的所有邻接边
        ll u = head[pos];
        while (u != -1) {
            ll to = e[u].to;  // 邻接点编号
            ll w = e[u].w;    // 边的权值
            if (dis[to] > w + d) {  // 如果找到更短的路径
                dis[to] = w + d;    // 更新最短距离
                q.push({dis[to], to}); 
            }
            u = e[u].next;  // 继续遍历下一个邻接点
        }
    }
    for (int i = 1; i <= n; i++) 
	{
        if (dis[i] == 0x3f3f3f3f3f3f3f3f) //如果数据类型是long long 那么就是0x3f3f3f3f3f3f3f3f,如果是int 那么就是0x3f3f3f3f 
            cout << "INF" << " ";
        else
            cout << dis[i] << " "; 
    }
    cout << endl;  // 换行
}
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0); 
    cin >> n >> m >> s;
    init();  // 初始化

    for (ll i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w);  
    }


    dijkstra();

    return 0;
}