题解 P4568 【[JLOI2011]飞行路线】

眠ㅤㅤㅤ · 2018-09-02 12:17:55 · 个人记录

#include<bits/stdc++.h>
#define Inf 0x3F3F3F3F
typedef long long LL;
using namespace std;

const int SIZE = 5E6 + 7;
struct Edges {
    int to, w, next;
} edge[SIZE];
int head[SIZE], cnt;
int dis[SIZE];

void Add(int form, int to, int w = 0) {
    edge[cnt].to = to, edge[cnt].next = head[form];
    edge[cnt].w = w; head[form] = cnt++;
}

void init(int sta) {
    memset(head, -1, sizeof head);
    memset(dis, 0x3F, sizeof dis);
    dis[sta] = 0;
}

void Dijkstra(int sta) {
    priority_queue<pair<int, int> > que; que.push(make_pair(0, sta));
    while (!que.empty()) {
        int now = que.top().second; que.pop();
        for (int pos = head[now]; ~pos; pos = edge[pos].next)
            if (dis[edge[pos].to] > dis[now] + edge[pos].w) {
                dis[edge[pos].to] = dis[now] + edge[pos].w;
                que.push(make_pair(-dis[edge[pos].to], edge[pos].to));
            }
    }
}

int main() {
    int N, M, K, S, E; scanf("%d%d%d%d%d", &N, &M, &K, &S, &E);
    init(S);
    int form, to, w;
    for (int pos = 1; pos <= M; pos++) {
        scanf("%d%d%d", &form, &to, &w);
        Add(form, to, w); Add(to, form, w);
        for (int Floor = 1; Floor <= K; Floor++) {
            Add(form + (Floor - 1) * N, to + Floor * N);
            Add(to + (Floor - 1) * N, form + Floor * N);

            Add(form + Floor * N, to + Floor * N, w);
            Add(to + Floor * N, form + Floor * N, w);
        }
    }
    Dijkstra(S);
    int ans = Inf;
    for (int Floor = 0; Floor <= K; Floor++)
        ans = min(ans, dis[E + Floor * N]);
    printf("%d\n", ans);
}