P348 最优贸易不能用 Dijkstra

Gesrua commented 5 years ago

因为转移从 + 变成 min ，似乎不能满足用 Dijkstra 的性质（就像不能跑负权一样？）

比如下面这组数据，跑正图时 dis[4] 应该为 2 但是程序输出 4（但是最后答案好像还是对的？）

// Author:XuHt
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int N = 100006, M = 1000006;
int n, m, tot = 0, Price[N];
int Head[N], Side[M], Next[M], ans[N];
int fHead[N], fSide[M], fNext[M], fans[N];
bool v[N], fv[N];
priority_queue<pair<int, int> > q;
priority_queue<pair<int, int> > fq;

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) scanf("%d", &Price[i]);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        Side[++tot] = y;
        Next[tot] = Head[x];
        Head[x] = tot;
        fSide[tot] = x;
        fNext[tot] = fHead[y];
        fHead[y] = tot;
        if (z == 2) {
            Side[++tot] = x;
            Next[tot] = Head[y];
            Head[y] = tot;
            fSide[tot] = y;
            fNext[tot] = fHead[x];
            fHead[x] = tot;
        }
    }
    memset(ans, 0x3f, sizeof(ans));
    memset(fans, 0xcf, sizeof(fans));
    ans[1] = Price[1];
    fans[n] = Price[n];
    q.push(make_pair(-ans[1], 1));
    fq.push(make_pair(fans[n], n));
    while (q.size()) {
        int x = q.top().second;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        for (int i = Head[x]; i; i = Next[i]) {
            int y = Side[i];
            if (ans[y] > ans[x]) {
                ans[y] = ans[x];
                ans[y] = min(ans[y], Price[y]);
                q.push(make_pair(-ans[y], y));
            }
        }
    }
    for (int i = 1; i <= n; ++i) cout << ans[i] << ' '; // 就是这里
    cout << endl;
    while (fq.size()) {
        int x = fq.top().second;
        fq.pop();
        if (fv[x]) continue;
        fv[x] = 1;
        for (int i = fHead[x]; i; i = fNext[i]) {
            int y = fSide[i];
            if (fans[y] < fans[x]) {
                fans[y] = fans[x];
                fans[y] = max(fans[y], Price[y]);
                fq.push(make_pair(fans[y], y));
            }
        }
    }
    int Ans = 0;
    for (int i = 1; i <= n; i++) Ans = max(Ans, fans[i] - ans[i]);
    cout << Ans << endl;
    return 0;
}

lydrainbowcat commented 5 years ago

Code fixed in commit a6c801c. 建议使用SPFA。使用Dijkstra的话需要允许一个点出队扩展多次（但复杂度会退化）。

xiaoh105 commented 5 years ago

@lydrainbowcat 可以用Dijkstra的，而且不需要扩展多次，我都A了，绝对没必要用SPFA的

lydrainbowcat commented 5 years ago

那就是数据弱吧，题目AC不能作为算法正确性的评判标准请给出使用Dijkstra的正确性证明

lydrainbowcat / tedukuri

P348 最优贸易不能用 Dijkstra #19