11138: 【原1138】主任是好人

题目描述

author: Wengong Jin 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1138

Description

话说主任在刷题的时候看到了这样一道题：

S国有N个城市，若干城市之间有道路连接，每条道路有一个坚固指数。现在T国要破坏S国若干条道路，使得城市1和城市N不连通。但是破坏道路需要费用，破坏所需的费用等于道路的坚固指数。于是T国的国王找到了你，希望你能帮助他完成这个任务。

主任当然知道这道题怎么做，但是主任对T国国王无礼的要求感到非常气愤。 “怎么可以把别人辛辛苦苦建造起来的道路就这样破坏掉呢！”

于是主任出了这样一道题：

S国有N个城市，若干城市之间有道路连接，每条道路由于比较陈旧，因此通过这条道路需要时间Ti。现在S国国王和T国国王成为了好伙伴，于是T国为了帮助S国的国民减少他们从城市1到城市N的时间，决定给S国修缮K条道路，使得这条道路通行时间为0。从而使得S国的国民从城市1到城市N的时间最短。于是T国的国王找到了你，希望你能帮助他完成这个任务。

主任当然知道这道题怎么做，但是主任不高兴做了，于是他就找到了你，让你解决掉这道题。

Input Format

第一行是正整数N，M，K，表示S国城市数量和道路数量，以及T国国王愿意修缮的道路数量K。

接着M行每行三个正整数，Xi，Yi，Ti，分别表示城市Xi与Yi之间有一条双向道路连接，并且所需时间是Ti。

Output Format

一行，即修缮完后从城市1到城市N所需的最短时间。

Sample Input1

Sample Output1

Limits

N<=10000, M<=50000, K<=20

1<=Xi,Yi<=N, 1<=Ti<=1000000

yyong119's solution

#include <cstdio>
#include <iostream>
#include <deque>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAX_N 10010
#define MAX_K 25
using namespace std;
struct Node {
    int tar, time;
    Node(int a = 0, int b = 0): tar(a), time(b) {}
};
int N, M, K;
int f[MAX_N][MAX_K];
vector<Node> link[MAX_N];
deque<int> q;
bool inque[MAX_N];
inline int read() {
    char ch = getchar(); int flag = 1, res = 0;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') res = res * 10 + ch - '0', ch = getchar();
    return res * flag;
}
inline bool cmp(const Node &p, const Node &q) {
    return p.time < q.time;
}
int main() {
    N = read(); M = read(); K = read();
    memset(f, 0x3f3f3f3f, sizeof(f));
    f[1][0] = 0;
    for (register int i = 0; i < M; ++i) {
        int x = read(), y = read(), t = read();
        link[x].push_back(Node(y, t));
        link[y].push_back(Node(x, t));
    }
    for (register int i = 0; i < N; ++i)
        sort(link[i].begin(), link[i].end(), cmp);
    q.push_back(1);
    while (!q.empty()) {
        int cur = q.front(); q.pop_front(); inque[cur] = false;
        for (register int i = 0; i < link[cur].size(); ++i) {
            int next = link[cur][i].tar, cost = link[cur][i].time;
            bool flag = false;
            for (register int j = 0; j <= K; ++j)
                if (f[cur][j] + cost < f[next][j]) {
                    f[next][j] = f[cur][j] + cost;
                    flag = true;
                }
            for (register int j = 0; j < K; ++j)
                if (f[cur][j] < f[next][j + 1]) {
                    f[next][j + 1] = f[cur][j];
                    flag = true;
                }
            if (!inque[next] && flag) {
                if (!q.empty() && f[next][K] >= f[q.front()][K]) q.push_back(next);
                else q.push_front(next);
                inque[next] = true;
            }
        }
    }
    printf("%d\n", f[N][K]);
    return 0;
}