1803. Shortest Path Faster(D4)

SWEA홈페이지 Solving Talk에 가면 홍준님이 올려주신 Shortest Path Faster Algorithm(SPFA) PDF 파일이 있다.(링크)

이 내용을 바탕으로 구했다.

SPFA는 평균적으로 O(E)의 수행복잡도를 보여주는 효과적인 알고리즘 이라고 한다.

#include <memory.h>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
int main()
{
    int T;
    setbuf(stdout, NULL);
    scanf("%d", &T);
    for (int test_case = 1; test_case <= T; test_case++)
    {
        int n, m, s, e;
        scanf("%d%d%d%d", &n, &m, &s, &e);
 
        vector< vector<pair<int, long long> > > v(n + 1);
 
        for (int i = 0; i < m; i++)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            v[a].push_back(make_pair(b, c));
            v[b].push_back(make_pair(a, c));
        }
        queue<int> q;//정점 리스트
        vector<int> inq(n + 1);
        vector<long long> d(n + 1);
        for (int i = 1; i <= n; i++)
            d[i] = 1e18;
        d[s] = 0;//시작점=0
        q.push(s);
 
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            inq[u] = 0;
            for (auto it = v[u].begin(); it != v[u].end(); it++)
            {
                if (d[u] + (*it).second < d[(*it).first])
                {
                    d[(*it).first] = d[u] + (*it).second;
                    if (inq[(*it).first] == 0)
                    {
                        q.push((*it).first);
                        inq[(*it).first] = 1;
                    }
                }
            }
        }
        long long ans = d[e];
 
        printf("#%d %lld\n", test_case, ans);
    }
    return 0;
}