1916

Created at : 2024-01-04 11:49
1916
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct SNode
{
    int64_t Next;
    int64_t Fee;
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int64_t n, m, Start, End, Fee;
    vector<int64_t> p;
    vector<vector<SNode>> BusInfo;
    vector<bool> IsVisited;
    cin >> n >> m;
    BusInfo.resize(n + 1);
    p.resize(n + 1);
    IsVisited.resize(n + 1);
    for(int64_t i = 0; i < n + 1; ++i)
    {
        p[i] = INT64_MAX;
        IsVisited[i] = false;
    }
    for(int64_t i = 0; i < m; ++i)
    {
        cin >> Start >> End >> Fee;
        BusInfo[Start].push_back({End, Fee});
    }
    cin >> Start >> End;
    for(int64_t i = 0; i < BusInfo[Start].size(); ++i)
    {
        p[BusInfo[Start][i].Next] = min(BusInfo[Start][i].Fee, p[BusInfo[Start][i].Next]);
    }
    IsVisited[Start] = true;
    while(true)
    {
        int64_t MinEdge = 0;
        for(int64_t i = 1; i < n + 1; ++i)
        {
            if(!IsVisited[i] && p[MinEdge] > p[i])
            {
                MinEdge = i;
            }
        }

        IsVisited[MinEdge] = true;
        if(IsVisited[End])
        {
            break;
        }

        for(int64_t i = 0; i < BusInfo[MinEdge].size(); ++i)
        {
            SNode Target = BusInfo[MinEdge][i];
            p[Target.Next] = min(p[Target.Next], p[MinEdge] + Target.Fee);
        }
    }

    cout << p[End];

    return 0;
}
1916

유형
