백준 1504 특정한 최단 경로

최단거리의 합 = 최단거리임을 파악하기.
1. v1 == 1 || v2 == n
2. 간선의 개수 = 0
이 두 가지 케이스에 대한 체크만 해주면 쉽게 풀리는 문제이다.

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

int n, e, v1, v2;
vector<vector<pii>> graph(801);
vector<int> dist(801, 1e9);

void dijkstra(int s) {
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    dist[s] = 0;
    pq.push({0, s});
    while (pq.size()) {
        int cost = pq.top().first;
        int now = pq.top().second;
        pq.pop();
        if (dist[now] < cost) continue;
        for (int i = 0; i < graph[now].size(); ++i) {
            int next = graph[now][i].first;
            int nextCost = cost + graph[now][i].second;
            if (dist[next] > nextCost) {
                dist[next] = nextCost;
                pq.push({nextCost, next});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> e;
    for (int i = 0; i < e; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    cin >> v1 >> v2;
    if (e == 0) {
        cout << -1;
        return 0;
    }
    int sp1 = 0, sp2 = 0;
    dijkstra(1);
    if (v1 == 1 || v2 == n) {
        cout << dist[n];
        return 0;
    }
    sp1 += dist[v1];
    sp2 += dist[v2];
    for (int i = 1; i <= n; ++i) dist[i] = 1e9;
    dijkstra(v1);
    sp1 += dist[v2];
    sp2 += dist[n];
    for (int i = 1; i <= n; ++i) dist[i] = 1e9;
    dijkstra(v2);
    sp1 += dist[n];
    sp2 += dist[v1];
    int ans = min(sp1, sp2);
    if (ans >= 1e9) cout << -1;
    else cout << ans;
}

수정 1.
for (int i = 1; i <= n; ++i) dist[i] = 1e9; 이 부분을
fill(dist.begin()+1, dist.begin()+n+1, 1e9);로 바꿨는데 시간단축이 되진 않았다. ㅠ

수정 2.
궁금해서 fill의 구현체를 찾아보았다.

template <class OutputIterator, class Size, class T>
  OutputIterator fill_n (OutputIterator first, Size n, const T& val)
{
  while (n > 0) {
    *first = val;
    ++first; --n;
  }
  
  return first;     // since C++11
}

흠...