弱化版AC,标准版68分求助

P4779 【模板】单源最短路径(标准版)

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一块放入堆中


|