Geirangerfjard @ 2023-04-02 10:12:04
RT,32pts
#include <iostream>
#include <cstring>
#include <queue>
#define int long long
const int N = 1400100;
using namespace std;
int n, m, s, jud;
int dist[N];
int h[N], ne[N], to[N], e[N], idx;
bool st[N];
queue <int> q;
int qpow(int a, int n)
{
int ans = 1;
while (n)
{
if(n & 1) ans *= a;
n >>= 1;
a *= a;
}
return ans;
}
void add(int a, int b, int w)
{
to[idx] = b;
e[idx] = w;
ne[idx] = h[a];
h[a] = idx ++;
}
void spfa()
{
memset(dist, 0x3f, sizeof dist);
jud = dist[0];
dist[s] = 0;
q.push(s);
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int b = to[i];
if (dist[b] > dist[t] + e[i])
{
dist[b] = dist[t] + e[i];
if (!st[b])
{
st[b] = true;
q.push(b);
}
}
}
}
//if (dist[n] == 0x3f3f3f3f) cout << "impossible" << endl;
//else cout << dist[n] << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
memset(h, -1, sizeof h);
cin >> n >> m >> s;
while (m -- )
{
int a, b, w;
cin >> a >> b >> w;
add(a, b, w);
//add(b, a, w);
}
spfa();
for (int i = 1; i <= n; i ++ )
{
if (dist[i] == jud) cout << qpow(2, 31) - 1 << " ";
else cout << dist[i] << " ";
}
}
by FuckYouJinhai @ 2023-04-02 10:19:12
@Alone_Helpless 是的,本题卡了s↗P↘F↑a↓,如有需要,请移步弱化版。
by Geirangerfjard @ 2023-04-02 10:20:36
@FiveFourierTransform 听说优化能过,但我不会qwq
by FuckYouJinhai @ 2023-04-02 10:23:47
@Alone_Helpless 实用性不强吧,,,
参考这个https://www.zhihu.com/question/292283275/answer/2824896940 ,不过好像要西加加一十七的语言标准
by UncleSam_Died @ 2023-07-10 07:30:59
@Alone_Helpless 能,但要加优化,用SLF能过
by zzb1217 @ 2023-08-04 12:03:52
要加优化