백준 10282 해킹 C++

간단한 해설

 

단순하게 다익스트라를 하면 된다. (c에서 시작해서, b->a로 이어지는데, s초가 더해진다.)

그러나 단순하게 2차원 배열로 그래프를 만들면 25%정도에서 메모리 초과가 발생한다.

나는 그래서 연결리스트로 풀 수 있지만 꼼수로 다음과 같이 그래프 연결이 필요한 부분만 연결하였다.

vector<vector<pair<ll,ll>>> graph(n+1,vector<pair<ll,ll>>());
for(int i=0;i<d;++i){
    ll a,b,s;
    cin>>a>>b>>s;
    graph[b].push_back({a,s});
}

 

답

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t-->0){
        ll n,d,c;
        cin>>n>>d>>c;
        vector<vector<pair<ll,ll>>> graph(n+1,vector<pair<ll,ll>>());
        for(int i=0;i<d;++i){
            ll a,b,s;
            cin>>a>>b>>s;
            graph[b].push_back({a,s});
        }
        priority_queue<pair<ll,ll>> q;
        q.push({0,c});
        pair<ll,ll> ans={0,0};//gae,time
        vector<ll> visited(n+1,987654321);
        visited[c]=0;
        while(!q.empty()){
            ll time=-q.top().first;
            ll idx=q.top().second;
            q.pop();
            for(int i=0;i<graph[idx].size();++i){
                if(graph[idx][i].second+time<visited[graph[idx][i].first]){  
                    visited[graph[idx][i].first]=graph[idx][i].second+time;
                    q.push({-visited[graph[idx][i].first],graph[idx][i].first});
                }
            }
        }
        for(int i=1;i<=n;++i){
            if(visited[i]<987654321){
                ++ans.first;
                ans.second=max(ans.second,visited[i]);
            }
        }
        cout<<ans.first<<" "<<ans.second<<"\n";
    }
}