백준 1238 파티 혼내주기

 

처음에 생각없이 플로이드로 풀었다가 TLE.
두번째로 m값이 생각보다 작아서 다익스트라를 n번 돌려서 풀었는데,
고수들의 코드를 보니 정방향 역방향으로 한번씩만 돌리면 풀리는걸 보고 한 수 배웠다.
아마 m값이 100000이었으면 내 무식한 방법은 또 TLE였겠지...

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

vector<pair<int, int> > adj[1001];
vector<pair<int, int> > rev[1001];
int arr[1001], dist[1001];
int n, m, x;

void input() {
    fastio;
    cin >> n >> m >> x;
    int a, b, c;
    for(int i = 1; i <= m; ++i) {
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        rev[b].push_back({c, a});
    }
}

void dijkstra(vector<pair<int, int> >(&graph)[1001]) {
    memset(dist, 0x3f, sizeof(dist));
    dist[x] = 0;
    priority_queue<pair<int, int> > pq;
    pq.push({0, x});
    while(!pq.empty()) {
        auto top = pq.top(); pq.pop();
        if(-top.first > dist[top.second]) continue;
        for(auto to : graph[top.second]) {
            int nDist = -top.first + to.first;
            if(nDist >= dist[to.second]) continue;
            dist[to.second] = nDist;
            pq.push({-nDist, to.second});
        }
    }
    for(int i = 1; i <= n; ++i) arr[i] += dist[i];
}

int main() {
    input();

    dijkstra(adj);
    dijkstra(rev);

    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans = max(ans, arr[i]);
    }  
    cout << ans;
}

 

근데 최적화된 플로이드로 풀리긴 풀린다.
종만북에서 공부한 방법으로 i와 k가 연결되지 않았을 때 스킵하면 된다.

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
using namespace std;

int adj[1001][1001];
int n, m, x;

void input() {
    fastio;
    cin >> n >> m >> x;
    int a, b, c;
    for(int i = 1; i <= m; ++i) {
        cin >> a >> b >> c;
        adj[a][b] = c;
    }
    for(int i = 1; i <= n; ++i) adj[i][i] = 0;
}

int main() {
    memset(adj, 0x3f, sizeof(adj));
    input();

    for(int k = 1; k <= n; ++k) {
        for(int i = 1; i <= n; ++i) {
            if(adj[i][k] > 1e9) continue;
            for(int j = 1; j <= n; ++j) {
                if(adj[i][k] && adj[k][j]) 
                    adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);
            }
        }
    }

    int ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans = max(ans, adj[i][x] + adj[x][i]);
    }
    cout << ans;    
}