AcWing 1475. 紧急情况（dijkstra + 堆优化 + 邻接表）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1475. 紧急情况（dijkstra + 堆优化 + 邻接表）原题链接中等

作者：

以凝 , 2020-10-28 00:18:49 , 所有人可见 , 阅读 1319

4

3

题目描述

作为城市的紧急救援团队负责人，你将获得一张你所在国家的特殊地图。

该地图显示了一些通过道路连接的分散城市，道路是双向的。

地图上标出了每个城市的救援队数量以及每对城市之间的每条道路的长度。

当其他城市发出紧急求援信息时，你的工作是尽快带领你的士兵前往该地点，同时，在途中尽可能多地调动救援帮手。
输入格式
第一行包含四个整数 N，表示城市数量（城市编号从 0 到 N−1），M 表示道路数量，C1 表示你当前所在的城市编号，C2 表示发出紧急求援信息的城市编号。

第二行包含 N 个整数，其中第 i 个整数表示城市 i 的救援队数量。

接下来 M 行，每行包含三个整数 c1,c2,Li，表示城市 c1 和城市 c2 之间存在一条道路相连，道路长度为 Li。

数据保证 C1 和 C2 之间至少存在一条路径相连。

输出格式
共一行，两个整数，第一个整数表示 C1 和 C2 之间最短路的数量，第二个整数表示走最短路的情况下，能聚集到的救援队最大数量。

数据范围
$2≤N≤500$ ,
$1≤M≤600$ ,
$1≤L_i≤200$ ,
每个城市包含的救援人员数量不超过 200。

样例

输入：

输出样例：

2 4


#include<bits/stdc++.h>  // 邻接表 + 堆优化
using namespace std ;
typedef pair<int , int > PII ;
const int N = 510 , M = N*N;
int weight[N] ;  // 原生数据，存消防队
int st[N] ;   // 判断集合
int num[N] ;  // 存最短路数量
int d[N]  ;   //存最短距离
int n , m , sr , ed ;
int w[N] ; // 最多的消防队
int h[N] , e[M] , ne[M] , idx , W[M]; // 距离; 
void add(int a , int b  ,int c ) 
{
    W[idx] = c , e[idx] = b , ne[idx] = h[a] , h[a] = idx++ ;
}

void dijkstra(int s )
{
    memset(d,0x3f,sizeof d) ;
    d[s] = 0 ;
    num[s] = 1 ;
    w[s] = weight[s] ; 

    priority_queue<PII ,vector<PII> ,greater<PII>>  q ; // 小根堆
    q.push({0,s});
    while(q.size())
    {
        auto t = q.top() ;
        q.pop();
        int ver = t.second , dis = t.first ;  // 建议小根堆存储pair 
        if(st[ver]) continue;
        st[ver] = 1 ;
        for(int i = h[ver] ;~i ; i= ne[i] )
        {
            int j = e[i] , k = W[i] ;

            if(d[j] > dis + k )
            {
                d[j] = dis + k;
                num[j]= num[ver] ;
                w[j] = w[ver] +  weight[j] ; 
                q.push({d[j] , j }) ;
            }
            else if(d[j] == dis + k )
            {
                if(w[j] < w[ver] +  weight[j])
                w[j] = w[ver] +  weight[j] ; 
                num[j] += num[ver] ;
            }
        }
    }
}
int main() 
{
    memset(h,  -1 , sizeof h ) ;
    cin >> n >> m >> sr >> ed ;
    for(int i = 0 ; i < n ; i ++ )
    {
        cin >> weight[i] ;
    }
    for(int i = 0 ; i < m ; i ++ )
    {
        int a , b , w ;
        cin >> a >>b >> w ;
       add(a, b ,w) , add(b,a ,w) ;

    }
    dijkstra(sr) ;
    cout << num[ed] << " " << w[ed] ;
    return 0 ;
}

5 评论

sangkun 2021-04-22 13:36

过不了全部数据

以凝 2021-04-22 21:44

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

const int N = 510, M = N * N ;

typedef pair<int, int> PII;

int n, m, s, d;
int sum[N], total[N], pw[N];
int h[N], e[M], ne[M], idx, w[M]; 
bool st[N];
int dist[N];
int pre[N];

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}


void dijkstra(int s) {

    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    total[s] = 1;
    sum[s] = pw[s];

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({dist[s], s});

    while(q.size()) 
    {
        auto t = q.top();
        q.pop();

        int ver = t.y, dis = t.x;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; ~i ; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dis + w[i]) 
            {
                dist[j] = dis + w[i];
                total[j] = total[ver];
                sum[j] = sum[ver] + pw[j];
                pre[j] = ver;

                q.push({ dist[j] , j});
            }
            else if (dist[j] == dis + w[i]) {
                total[j] += total[ver];
                if (sum[j] < sum[ver] + pw[j]) {
                    sum[j] = sum[ver] + pw[j];
                    pre[j] = ver;
                }
            }
        }
    }
}


int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m >> s >> d;
    for (int i = 0; i < n; i ++ ) scanf("%d", &pw[i]);
    int a, b, c;
    for (int i = 1; i <= m; i ++ ) 
    {    
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    } 
    dijkstra(s);
    cout << total[d] << ' ' << sum[d] << endl;
    return 0;
}

sangkun 2021-04-22 21:52 回复了以凝的评论

谢谢

以凝 2021-04-22 23:21 回复了 sangkun 的评论

不客气~

sangkun 2021-04-22 13:36

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

const int N = 510, M = N * N * 2;

typedef pair<int, int> PII;

int n, m, s, d;
int sum[N], total[N], pw[N];
int h[N], e[M], ne[M], idx, w[M]; 
bool st[N];
int dist[N];
int pre[N];

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}

void output(int s, int d) {
    if (s == d) {
        printf("%d", s);
        return ;
    } else {
        output(pre[s], d);
        printf(" %d", s);
    }
}

void dijkstra(int s) {

    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    total[s] = 1;
    sum[s] = pw[s];

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({s, dist[s]});

    while(q.size()) {
        auto t = q.top();
        q.pop();

        int ver = t.x, dis = t.y;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i]) {
            int j = e[i];
            if (dist[j] > dis + w[i]) {
                dist[j] = dis + w[i];
                total[j] = total[ver];
                sum[j] = sum[ver] + pw[j];
                pre[j] = ver;

                q.push({j, dist[j]});
            }
            else if (dist[j] == dis + w[i]) {
                total[j] += total[ver];
                if (sum[j] < sum[ver] + pw[j]) {
                    sum[j] = sum[ver] + pw[j];
                    pre[j] = ver;
                }
            }
        }
    }
}


int main() {
    memset(h, -1, sizeof h);
    cin >> n >> m >> s >> d;
    for (int i = 0; i < n; i ++ ) scanf("%d", &pw[i]);
    int a, b, c;
    for (int i = 1; i <= m; i ++ ) {    
        scanf("%d %d %d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    } 
    dijkstra(s);
    cout << total[d] << ' ' << sum[d] << endl;
    output(d, s);
    return 0;
}

求帮忙看看问题在哪里

App 内打开