[백준 1753] 최단경로

백준 1753 최단경로

처음에 짤땐 모든 간선을 넣을려 하지 않고 중복된 간선이 있을 수 있어서 최소비용 간선으로 갱신을 하는 소스를 짰더니 0.7~0.9초까지 나왔다. 이 갱신하는 부분을 지우고 제출해보니깐 시간이 0.2초까지 줄어들었다.

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
const int INF = 0x3f3f3f3f;
 
vector<vector<pair<int, int>>> map;
vector<bool> visit;
vector<int> ans;
priority_queue<pair<int, int>> pq;
 
int main()
{
    int v, e;
    int start;
    scanf("%d %d %d", &v, &e, &start);
    int from, to, cost;
    map.resize(v + 1);
    ans.resize(v + 1);
    for (int i = 0; i < v + 1; i++)ans[i] = INF;
 
    for (int i = 0; i < e; i++)
    {
        scanf("%d %d %d", &from, &to, &cost);
        
        map[from].push_back(make_pair(to, cost));
    }
 
    pq.push(make_pair(0, start));
    ans[start] = 0;
 
    while (!pq.empty())
    {
        pair<int, int> now = pq.top(); pq.pop();
        now.first *= -1;
        if (now.first > ans[now.second])continue;
        for (int i = 0; i < map[now.second].size(); i++)
        {
            if (ans[map[now.second][i].first] > ans[now.second] + map[now.second][i].second)
            {
                ans[map[now.second][i].first] = ans[now.second] + map[now.second][i].second;
                pq.push(make_pair(-map[now.second][i].second, map[now.second][i].first));
            }
        }
    }
 
    for (int i = 1; i <= v; i++)
    {
        if (ans[i] == INF)
        {
            printf("INF\n");
        }
        else
        {
            printf("%d\n", ans[i]);
        }
    }
 
    return 0;
}

아래 코드는 SPFA로 푼 소스이다. (푼 이유는 그냥 SPFA 공부하려고...)

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
const int INF = 0x3f3f3f3f;
 
vector<vector<pair<int, int>>> map;
vector<int> ans;
vector<int> InQ;
queue<int> q;
 
int main()
{
    int v, e;
    scanf("%d %d", &v, &e);
    int start;
    scanf("%d", &start);
 
    ans.resize(v + 1);
    InQ.resize(v + 1);
    map.resize(v + 1);
    fill(InQ.begin(), InQ.end(), false);
    fill(ans.begin(), ans.end(), INF);
    for (int i = 0; i < e; i++)
    {
        int from, to, end;
        scanf("%d %d %d", &from, &to, &end);
        map[from].push_back(make_pair(to, end));
    }
 
    q.push(start);
    InQ[start] = 1;
    ans[start] = 0;
 
    while (!q.empty())
    {
        int now = q.front(); q.pop();
        InQ[now] = false;
 
        for (int i = 0; i < map[now].size(); i++)
        {
            if (ans[now] + map[now][i].second < ans[map[now][i].first])
            {
                ans[map[now][i].first] = ans[now] + map[now][i].second;
                if (!InQ[map[now][i].first])
                {
                    InQ[map[now][i].first] = true;
                    q.push(map[now][i].first);
                }
            }
        }
    }
 
    for (int i = 1; i <= v; i++)
    {
        if (ans[i] == INF)printf("INF\n");
        else printf("%d\n", ans[i]);
    }
    return 0;
}