Tang__Bin @ 2023-01-17 08:20:47
源代码如下:
#pragma optimize("2")
#define IOS() ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
#define endl "\n"
struct E
{
int tn;
int dis;
};
int sw[100010], vis[100010];
struct cmp
{
bool operator()(int& n1, int& n2)const
{
return sw[n1] > sw[n2];
}
};
priority_queue < int, vector<int>, cmp> q;
vector<vector<E>> es;
int main()
{
IOS();
int n, m, s; cin >> n >> m >> s;
es.resize(n + 2);
memset(vis, false, sizeof(vis));
int n1; E e0={0,0};
for (int i = 0; i < m; i++)
{
cin >> n1 >> e0.tn >> e0.dis;
es[n1].push_back(e0);
}
for (int i = 0; i <= n; i++)sw[i] = 0x7fffffff;
sw[s] = 0;
q.push(s);
int fnode, tnode, wfe, wtn;
while (!q.empty())
{
fnode = q.top();
q.pop();
if (vis[fnode])continue;
vis[fnode] = true;
for (E ei : es[fnode])
{
tnode = ei.tn;
wfe = sw[fnode] + ei.dis;
wtn = sw[tnode];
if (wfe < wtn) { sw[tnode] = wfe; q.push(tnode); }
}
}
for (int i = 1; i < n; i++)cout << sw[i] << ' ';
cout << sw[n] << endl;
return 0;
}
感觉比较和计算什么的都对,但还是WA,不知怎么错的
by _CY_ @ 2023-01-17 08:34:42
开long long
by _CY_ @ 2023-01-17 08:35:04
sw会爆int
by Tang__Bin @ 2023-01-17 18:49:39
@CY 还是68分。。。
by _CY_ @ 2023-02-02 10:04:45
这种写法可能有些问题,你的sw数组是时时改变的,这样会导致堆出现问题.最好将sw和tnode作为一个pair一块放入堆中