algorithmStudy/10282.cpp at master · judy5050/algorithmStudy · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//
//  10282.cpp
//  algo
//
//  Created by 박효정 on 2021/07/23.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 10001
using namespace std;

vector<int>dis(MAX);
vector<pair<int, int>>graph[MAX];
void dijkstra(int start){
    priority_queue<pair<int,int>>pq;
    pq.push({0,start});
    dis[start]=0;
    while(!pq.empty()){
        int now=pq.top().second;
        int val=-pq.top().first;
        pq.pop();
        if(dis[now]<val) continue;;
        for(int i=0;i<graph[now].size();i++){
            if(val+graph[now][i].second<dis[graph[now][i].first]){
                dis[graph[now][i].first]=val+graph[now][i].second;
                pq.push({-(val+graph[now][i].second),graph[now][i].first});
            }


        }


    }


}

void init(){

    fill(dis.begin(), dis.end(), 987654321);
    for(int i=0;i<MAX;i++){
        graph[i].clear();
    }

}


int main(){
    cin.tie(0);
    cout.tie(0);
    std::ios::sync_with_stdio(false);


    //test case 수
    int c;
    cin>>c;

    while(c--){
        int n,d,c;
        cin>>n>>d>>c;
        init();
        for(int i=0;i<d;i++){
            int a,b,s;
            cin>>a>>b>>s;
            graph[b].push_back({a,s});


        }


        dijkstra(c);
        int res=0;
        int cnt=0;
        for(int i=1;i<=n;i++){
            if(dis[i]!=987654321){
                res=max(res,dis[i]);
                cnt++;
            }
        }

        cout<<cnt<<' '<<res<<"\n";


    }


    return 0;
}