题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;

const int N = 2510, M = 6210 * 2;
int h[N], e[M], w[M], ne[M], idx;
int n, c, ts, te;
int dist[N];
bool st[N];



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

int dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(dist, 0x3f, sizeof dist);

    heap.push({0, ts});
    dist[ts] = 0;

    while(heap.size())
    {
        auto t = heap.top();
        heap.pop();
        if (t.second == te) return t.first;
        if (st[t.second]) continue;
        st[t.second] = true;
        int d = t.first, u = t.second;

        for (int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i], width = w[i];
            if (dist[j] > d + width)
            {
                dist[j] = d + width;
                heap.push({dist[j], j});
            }
        }
    }
    return -1;
}

int main()
{
    cin >> n >> c >> ts >> te;

    memset(h, -1, sizeof h);

    while(c --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    cout << dijkstra() << endl;
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int, int> PII;

const int N = 2510, M = 6210 * 2;
int h[N], e[M], w[M], ne[M], idx;
int n, c, ts, te;
int dist[N];
bool st[N];



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

int spfa()
{
    memset(dist, 0x3f, sizeof dist);

    queue<int> q;
    q.push(ts);
    dist[ts] = 0;
    st[ts] = true;

    while(q.size())
    {
        auto t = q.front();
        q.pop();
        st[ts] = false;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], d = w[i];
            if (dist[j] > dist[t] + d)
            {
                dist[j] = dist[t] + d;
                if (!st[j]) q.push(j);
            }
        }
    }
    return dist[te];
}

int main()
{
    cin >> n >> c >> ts >> te;

    memset(h, -1, sizeof h);

    while(c --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }

    cout << spfa() << endl;
    return 0;
}