Problem D. Dwarf Tower spfa

http://codeforces.com/gym/100269/attachments

首先建图，然后图中每条边的权值是会变化的，是由dis[x] + dis[y]  --->   dis[make]，然后就相当于新增加一个原点0，求0到1的最短距离

如果用了2更新4失败，但是2本来不是最优的，就是可以用7和8使得更优，那这样会不会漏掉最优解？答案是不会的，因为使用到7和8能更新2得时候，就会把2重新丢尽队列

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int maxn = 2e5 + ;

struct Edge {

    int u, v, w, tonext;

}e[maxn * ];

int first[maxn], num;

void addEdge(int u, int v, int w) {

    ++num;

    e[num].u = u, e[num].v = v, e[num].w = w, e[num].tonext = first[u];

    first[u] = num;

}

LL dis[maxn];

int in[maxn], tim[maxn];

bool spfa(int bx, int n) { //从bx开始，有n个顶点

    queue<int> que;

    while (!que.empty()) que.pop();

    for (int i = ; i <= n; ++i) {

        que.push(i);

        in[i] = true;

        tim[i]++;

    }

    while (!que.empty()) {

        int u = que.front();

        if (tim[u] > n) return true; //入队次数超过n次，出现负环

        que.pop();   //in[u] = false ?

        for (int i = first[u]; i; i = e[i].tonext) {

            if (dis[e[i].v] > dis[e[i].u] + dis[e[i].w]) {

                dis[e[i].v] = dis[e[i].u] + dis[e[i].w];

                if (!in[e[i].v]) { //不在队列

                    que.push(e[i].v);

                    in[e[i].v] = true;

                    tim[e[i].v]++;

                }

            }

        }

        in[u] = false;

    }

    return false;

}

void work() {

    int n, m;

    cin >> n >> m;

    for (int i = ; i <= n; ++i) {

        cin >> dis[i];

    }

    for (int i = ; i <= m; ++i) {

        int f, x, y;

        cin >> f >> x >> y;

        addEdge(x, f, y);

        addEdge(y, f, x);

    }

    spfa(, n);

    cout << dis[] << endl;

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    freopen("dwarf.in", "r", stdin);

    freopen("dwarf.out", "w", stdout);

    IOS;

    work();

    return ;

}

也可以贪心。

每次都取一个权值最小的出来，因为那个已经不可能更小了，直接删除，然后更新其他。

用set维护。dp

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

struct Node {

    LL cost, id;

    bool operator < (const struct Node & rhs) const {

        if (cost != rhs.cost) return cost < rhs.cost;

        else return id < rhs.id;

    }

    Node(LL _cost, LL _id) {

        cost = _cost, id = _id;

    }

};

set<Node>ss;

const int maxn = 1e6 + ;

LL dp[maxn];

vector<pair<int, int> > vc[maxn];

int getid[maxn];

void work() {

    int n, m;

    cin >> n >> m;

    for (int i = ; i <= n; ++i) {

        int val;

        cin >> val;

        dp[i] = val;

        ss.insert(Node(val, i));

    }

    for (int i = ; i <= m; ++i) {

        int a, b, c;

        cin >> a >> b >> c;

        vc[c].push_back(make_pair(b, a));

        vc[b].push_back(make_pair(c, a));

    }

    set<Node> :: iterator it;

    while (!ss.empty()) {

        it = ss.begin();

        LL id = it->id;

        LL cost = it->cost;

        ss.erase(it);

        for (int i = ; i < vc[id].size(); ++i) {

            int an = vc[id][i].first, to = vc[id][i].second;

            if (!ss.count(Node(dp[to], to))) {

                continue;

            }

            ss.erase(Node(dp[to], to));

            dp[to] = min(dp[to], cost + dp[an]);

            ss.insert(Node(dp[to], to));

        }

    }

    printf("%lld\n", dp[]);

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#else

    freopen("dwarf.in","r",stdin);

    freopen("dwarf.out","w",stdout);

#endif

    work();

    return ;

}