美文网首页PAT
GPLT L2-001. 紧急救援 dijkstra

GPLT L2-001. 紧急救援 dijkstra

作者: 无令便逐风 | 来源:发表于2018-03-28 10:00 被阅读1次

题目链接戳这里
dijkstra模板,源点到点i,经u有更短路,更新到i的救援队数cjy[i]=cjy[u]+jy[i],更新到点i的路径数ts[i]=ts[u]
若经u是原先到i的同等长度的路径,路径之间是平等关系,和起来: ts[i] += ts[u],同理更新一下其它值,注意同等长度遇到救援队数更多时要修改路径.


#include <bits/stdc++.h>
#include <iostream>
using namespace std;

#define mst(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
const int inf = 0x3f3f3f3f, maxN = 505;
int N, M, S, D;
// 城市存的救援人数 图 是否已在集合S中的标记
int jy[maxN], G[maxN][maxN], ins[maxN];
// 到i城路径条数 到i城的救援人数 前一个节点 最短距离d
int ts[maxN], cjy[maxN], pre[maxN], d[maxN];

void dijkstra(int s) {
    mst(ins, 0);
    mst(d, inf);
    mst(cjy, 0);
    mst(pre, -1);
    mst(ts, 0);
    cjy[s] = jy[s];
    ts[s] = 1;
    d[s] = 0;

    while (1) {
        int u = -1;
        rep(i, 0, N)
            if (!ins[i] && (u == -1 || d[i] < d[u]))
                u = i;
        if (u == -1)
            break;
        ins[u] = 1;
        rep(i, 0, N) {
            if (!ins[i] && G[u][i] < inf) {
                if (d[u] + G[u][i] < d[i]) {
                    d[i] = d[u] + G[u][i];
                    pre[i] = u;
                    cjy[i] = cjy[u] + jy[i];
                    ts[i] = ts[u];
                } else if (d[u] + G[u][i] == d[i]) {
                    ts[i] += ts[u];
                    if (cjy[u] + jy[i] > cjy[i]) {
                        cjy[i] = cjy[u] + jy[i];
                        pre[i] = u;
                    }
                }
            }
        }
    }
}

void print_path(int e) {
    int rec[maxN], idx = 0;
    while (e != -1) {
        rec[idx++] = e;
        e = pre[e];
    }
    rep(i, 0, idx) {
        if (i) printf(" ");
        printf("%d", rec[idx - 1 - i]);
    }
}

int main() {
    // freopen("data.in", "r", stdin);
    scanf("%d%d%d%d", &N, &M, &S, &D);
    rep(i, 0, N) scanf("%d", &jy[i]);

    int from, to, dis;
    mst(G, inf);
    rep(i, 0, M) {
        scanf("%d %d %d", &from, &to, &dis);
        G[from][to] = G[to][from] = dis;
    }
    dijkstra(S);
    printf("%d %d\n", ts[D], cjy[D]);
    print_path(D);

    return 0;
}

相关文章

  • 2018-03-13 L2

    L2-001. 紧急救援谢谢大佬代码dijkstra spfadr

  • GPLT L2-001. 紧急救援 dijkstra

    题目链接戳这里dijkstra模板,源点到点i,经u有更短路,更新到i的救援队数cjy[i]=cjy[u]+jy[...

  • 2018-03-19

    L2-002. 链表去重有时候 一直写不出来就重新写一遍吧。 L2-001. 紧急救援 我这道题败在 细节,还是 ...

  • 2018-03-21 第三周任务

    两种排序方式 L2-002. 链表去重有时候 一直写不出来就重新写一遍吧。 L2-001. 紧急救援 我这道题败在...

  • L2_001紧急救援(Dijkstra)

    作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。...

  • GPLT L3-011. 直捣黄龙 dijkstra

    题目链接戳这里和紧急救援差不多.用的dijkstra用的是map来映射值与名,名与值傻了一个小地方: 遇到同样长度...

  • 有小情而无大爱——《紧急救援》

    今天聊聊电影《紧急救援》。 片名 The Rescue(2020)。 《紧急救援》表现的主体是交通海上应急反应特勤...

  • 紧急救援

    今天早上,刚下过一阵小雨,空气好清新。小红车吃完早饭高高兴兴的出门了,他要到他姥姥家去玩,姥姥家在离着二...

  • 紧急救援

    这天的阳光别样的好,像天鹅绒毛一般的柔软,温暖,它无疑是冬日里大自然给予的最好的馈赠。和往常一样,小朋友们来到了户...

  • 紧急救援

    刚刚经历了惊心动魄的半小时紧急救援。现在我的手还在颤抖着。 刚吃过晚饭。还没来得及洗碗。就听到楼上邻居一片大声吵闹...

网友评论

    本文标题:GPLT L2-001. 紧急救援 dijkstra

    本文链接:https://www.haomeiwen.com/subject/bkcycftx.html