題目

給定一個 n 個點，m 條有向邊的帶非負權圖，請你計算從 s 出發，到每個點的距離。

輸入格式

第一行為三個正整數 n,m,s。第二行起 m 行，每行三個非負整數 u_i,v_i,w_i，表示從 u_i 到 v_i 有一條權值為 w_i 的有向邊。

輸出格式

輸出一行 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 ≤ 10⁵

1 ≤ m ≤ 2×10⁵

s = 1

1 ≤ u_i , v_i ≤ n

0 ≤ w_i ≤ 10⁹

0 ≤ ∑ w_i ≤ 10⁹

題解

思路

標準的Dijkstra，不解釋（然而第一次做時不會用優先佇列，所以爆零了）
值得一提的是，樸素Dijkstra的時間複雜度好像是 O( n² ) ，而優先佇列優化的時間複雜度好像是 O( m log m )，在選擇優不優化時看清資料範圍（即 m = n² 時，比如某道最小生成樹題，以後應該會發）。
程式碼是以前寫的，所以碼風和變數名不忍直視，甚至還出現了一些我自己都看不懂的蜜汁操作(
不過由於情懷問題還是發上來吧（其實是因為不想重新寫一遍），以後有時間再重寫。

程式碼

O( n² )：

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
int n,m,s,dis[10001],first[10001],next[500001];
bool vis[10001];
struct st
{
	int s,f,jz;
}a[500001];
int main()
{
	memset(dis,-1,sizeof(dis));
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a[i].s,&a[i].f,&a[i].jz);
		if(first[a[i].s]==0) first[a[i].s]=i;
		else
		{
			next[i]=first[a[i].s];
			first[a[i].s]=i;
		}
	}
	int p=first[s];
	while(p!=0)
	{
		if(dis[a[p].f]==-1) dis[a[p].f]=a[p].jz;
		else if(a[p].jz<dis[a[p].f]) dis[a[p].f]=a[p].jz;
		p=next[p];
	}
	dis[s]=0;
	dis[0]=2147483647;
	vis[s]=true;
	int sum;
	for(int i=2;i<=n;i++)
	{
		sum=0;
		for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]!=-1&&dis[j]<=dis[sum]) sum=j;
		if(sum==0) break;
		vis[sum]=true;
		p=first[sum];
		while(p!=0)
		{
			if(dis[sum]+a[p].jz<dis[a[p].f]||dis[a[p].f]==-1) dis[a[p].f]=dis[sum]+a[p].jz;
			p=next[p];
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(vis[i]) printf("%d ",dis[i]);
		else printf("2147483647 ");
	}
	return 0;
}

O( m log m )：

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<queue>
using namespace std;
#define N 999999999999999999
long long n,m,s,fi[100005],ne[200005],dis[100005],t;
bool vis[100005];
struct st
{
	long long s,f,jz;
}maap[200005];
struct no
{
	long long f,jz;
	bool operator < (const no &that) const
	{
		return jz>that.jz;
	}
}a;
priority_queue<no> q;
int main()
{
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=n;i++) dis[i]=N;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&maap[i].s,&maap[i].f,&maap[i].jz);
		ne[i]=fi[maap[i].s];
		fi[maap[i].s]=i;
	}
	a.f=s;
	a.jz=0;
	dis[s]=0;
	q.push(a);
	while(!q.empty())
	{
		while(!q.empty()&&vis[q.top().f]) q.pop();
		if(q.empty()) break;
		t=q.top().f;
		q.pop();
		vis[t]=true;
		t=fi[t];
		while(t!=0)
		{
			if(dis[maap[t].s]!=N&&dis[maap[t].f]>dis[maap[t].s]+maap[t].jz)
			{
				dis[maap[t].f]=dis[maap[t].s]+maap[t].jz;
				a.f=maap[t].f;
				a.jz=dis[maap[t].f];
				q.push(a);
			}
			t=ne[t];
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	return 0;
}