题目描述

最短路的简单拓展
写的有点怀疑人生
先放标答——朴素dijkstra
然后用两个数组分别维护更新最短路的数量和救援队的最大值。

算法1

(朴素版本dijkstra) $O(n^2)$

C++ 代码

#include <cstring>
#include <iostream>
using namespace std;
const int N = 610;
int n, m, c1, c2;
int g[N][N];
int dist[N], num[N], cnt[N], tot[N];
bool st[N];
void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[c1] = 0, cnt[c1] = 1, tot[c1] = num[c1];
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        for(int j = 0; j < n; j ++)
            if(st[j] == 0 && (t == -1 || dist[t] > dist[j]))
                t = j;
        st[t] = true;
        for(int j = 0; j < n; j ++)
        {
            if (st[j] == false && dist[j] == dist[t] + g[t][j])
            {
                cnt[j] += cnt[t];
                if (tot[j] < tot[t] + num[j]) tot[j] = tot[t] + num[j];
            }
            else if (st[j] == false && dist[j] > dist[t] + g[t][j])
            {
                dist[j] = dist[t] + g[t][j];
                cnt[j] = cnt[t];
                tot[j] = tot[t] + num[j];
            }
        }
    }
}
int main()
{
    cin >> n >> m >> c1 >> c2;
    for (int i = 0; i < n; i ++) cin >> num[i];
    memset(g, 0x3f, sizeof g);
    while(m --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = c;
    }
    dijkstra();
    cout << cnt[c2] << ' ' << tot[c2];
    return 0;
}

算法2

(堆优化版本的djkstra/spfa) $O(mlogn)/O(m)~O(nm)$

一开始写的是堆优化版本的dijkstra，结果在第五个点TLE了。我：？？？？

然后换了spfa，反正也没调对/。

反正到现在为止还没有调出来，也不知道问题出哪里了。

望大佬赐教/。

错 误 的！ C++ 代码

#pragma GCC optimize(2)
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;
const int N = 610;
int h[N], e[N], ne[N], w[N], cnt[N], tot[N], idx;
int n, m, c1, c2;
int dist[N];
int num[N];
bool st[N];
int read()
{
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++;
}
void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[c1] = 0, cnt[c1] = 1, tot[c1] = num[c1];
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, c1});
    while (heap.size())
    {
        PII t = heap.top(); heap.pop();
        int distance = t.first, ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;
        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > distance + w[i])
            {
                cnt[j] = cnt[ver];
                tot[j] = tot[ver] + num[j];
                dist[j] = distance + w[i];
                heap.push({dist[j], j});
            }
            else if (dist[j] == distance + w[i])
            {
                cnt[j] += cnt[ver];
                if (tot[j] < tot[ver]) tot[j] = tot[ver] + num[j];
            }
        }
    }
}
void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    dist[c1] = 0, st[c1] = true, cnt[c1] = 1, tot[c1] = num[c1];
    queue<int> q;
    q.push(c1);
    while(q.size())
    {
        int t = q.front(); q.pop();
        st[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                cnt[j] = cnt[t];
                tot[j] = tot[t] + num[j];
                dist[j] = dist[t] + w[i];
                if(st[j] == false)
                {
                    st[j] = true;
                    q.push(j);
                }
            }
            else if (dist[j] == dist[t] + w[i])
            {
                cnt[j] += cnt[t];
                if (tot[j] < tot[t]) tot[j] = tot[t] + num[j];
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    memset(h, -1, sizeof h);
    n = read(), m = read(), c1 = read(), c2 = read();
    for (int i = 0; i < n; i ++) num[i] = read();
    for (int i = 0; i < m; i ++)
    {
        int a, b, c;
        a = read(), b = read(), c = read();
        add(a, b, c), add(b, a, c);
    }
    dijkstra();
    cout << cnt[c2] << " " << tot[c2] << endl; 
}