48求dalao解答orz

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

Wjx12wjX @ 2024-02-23 01:20:46

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define lowbit(x) (x & ( -x ))
//#define i64 __int64
//typedef __int64 i64;
#define PII pair<ll,ll>
#define VCT vector 
typedef long long ll;
typedef unsigned long long ull;
const ll N = 1e6 + 10, mod = 1e9 + 7, INF = 0x3f3f3f3f;
ll a[N], summ[N], v[N], fa[N], in[N], b[N], num[N];
ll n, m, d, h, x, y, z, k, pre, cnt, res, len, tot, ans, sum, now, maxn = -1e18, minn = 1e18;
priority_queue <ll, vector<ll>, greater<ll> > pq;   //less 降序排列 优先队列
priority_queue <ll, vector<ll>, less<ll> > pq1;     //默认升序
string s, s1, s2, s3;
char ss[1000][1000];
VCT <ll> vis[N], vis1;
map <ll, ll> mp;
unordered_map <ll, ll> mpp, mp2;
PII pi[N];
bool ok[N];
ull qpow(ull a, ull n) {
    ull ans = 1;
    while (n) {
        if (n & 1)
            ans = (ans * a) % mod;
        a = (a * a) % mod;
        n >>= 1LL;
    }
    return ans;
}
 //快速幂
set <ll> PrimeZ(ll x) {
    set <ll> primeZ;
    for (int i = 2; i <= sqrt(x); i++) {
        if (x % i)  continue;
        primeZ.insert(i);
        while (x % i == 0)  x /= i;
    }
    if (x > 1)  primeZ.insert(x);
    return primeZ;
}
//分解质因数
ll ls(ll p) { return p << 1; }
ll rs(ll p) { return p << 1 | 1; }
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

void solve()
{
    cin >> n >> m >> cnt;
    map <PII, ll> mp;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> pre;
        vis[x].push_back(y);
        mp[{x, y}] = pre;
    }
    priority_queue <PII> p;
    p.push({ 0,cnt });
    for (int i = 0; i <= n; i++)    b[i] = INF;
    b[cnt] = 0;
    while (p.size()) {
        k = p.top().second;
        p.pop();
        if (ok[k])  continue;
        ok[k] = 1;
        for (auto i : vis[k]) {
            if (b[i] > b[k] + mp[{k, i}]) {
                b[i] = b[k] + mp[{k, i}];
                p.push({ -b[i],i });
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i] << ' ';
    }
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); std::cout.tie(0);
    //int t; cin >> t;
    //while (t--)
        solve();
    return 0;
}
/*

*/

by Wjx12wjX @ 2024-02-23 01:36:56

是因为空间炸了吗


by Terrible @ 2024-02-23 03:28:59

@Wjx12wjX

本题含有边权不同的重边。

if(mp.find({x, y})==mp.end())
    mp[{x, y}]=pre;
else mp[{x, y}]=min(pre,mp[{x, y}]);

吐槽一句:边和权不能用 VCT <PII> vis[N]; 存一块吗,遍历的时候直接 for(auto[i,w]:vis[k]),用 mp 的话时间开销太大了吧。


by Wjx12wjX @ 2024-02-23 12:56:03

@Terrible 已AC,感谢dalao orz 我的vs好像不能这样写

for(auto [i,w]: vis[k])

他会报错


by Terrible @ 2024-02-23 14:14:46

安装上新版编译器把 C++20 打开就没有这种问题了。


|