Silver Cow Party(최단거리 + Dijkstra + 인접 테이블 + 우선 순위 큐)

Silver Cow Party
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 11348
 
Accepted: 5077
Description
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.
Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow's return route might be different from her original route to the party since roads are one-way.
Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?
Input
Line 1: Three space-separated integers, respectively: 
N, 
M, and 
X 
Lines 2..
M+1: Line 
i+1 describes road 
i with three space-separated integers: 
Ai, 
Bi, and 
Ti. The described road runs from farm 
Ai to farm 
Bi, requiring 
Ti time units to traverse.
Output
Line 1: One integer: the maximum of time any one cow must walk.
Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Sample Output

10

Hint
Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.
 
제목:
N(1~1000), M(1~100000), X(1~N)을 제시하면 N곳, M길이 있고 목적지는 X이다.이후 M길을 제시하면 각 길은 단방향이며 A에서 B까지 T(1~100)의 시간이 걸린다는 것을 의미한다.모든 장소는 종점에 도착하고 종점에서 원래의 장소로 돌아가야 하며, 모든 길은 시간이 가장 짧아야 한다.이렇게 많은 장소 중 가장 긴 시간을 구하다.
 
생각:
최단로.딱 보니 Floyd인 줄 알았는데 TLE 이후 분석해보니 시간 복잡도 O(n^3)는 1000^3=10^9=10^7*100=1s*100100s의 시간입니다. 제목은 2000ms=2s입니다. 과감하게 시간을 초과하면 Floyd를 사용할 수 없습니다.그러므로 Dijkstra로 하나하나의 단원으로 최단로를 계산할 수 밖에 없다. 왜냐하면 마이너스 고리가 없기 때문에 Dijkstra를 사용한다.다음 시간 복잡도 요약(N은 노드 수, M은 모서리 수):
    Floyd :O(N ^ 3);
Dijkstra: 인접 행렬 O(N^2);인접표 + 우선 대기열: O(NlogN + M)가 우선 대기열에서 요소를 추출하는 것은logN입니다. 모두 N번을 추출해야 하기 때문에 NlogN입니다. 매번 최대 M개의 가장자리를 옮겨야 하기 때문에 NlogN + M입니다.
    Bellman Ford :O(N * M);
    SPFA :O(kM)= O(M);
따라서 Dikstra 인접표 + 우선 대기열로 제목 요구를 충족시킬 수 있습니다.   
 
    AC:

#include <cstdio>
#include <queue>
#include <utility>
#include <iostream>
#include <string.h>
#include <vector>
#define MAX 100005
#define INF 99999999
using namespace std;

typedef pair<int,int> pii;

int v[MAX],w[MAX],fir[1005],next[MAX];
int d[1005][1005],vis[1005];
int ind,n;

void add_edge(int f,int t,int val) {
    v[ind] = t;
    w[ind] = val;
    next[ind] = fir[f];
    fir[f] = ind;
    ind++;
}

void Dijstra(int s) {
    for(int i = 1;i <= n;i++)   d[s][i] = INF;
    memset(vis,0,sizeof(vis));
    d[s][s] = 0;
    priority_queue<pii,vector<pii>,greater<pii> > q;
    q.push(make_pair(d[s][s],s));
    while(!q.empty()) {
        pii k = q.top();q.pop();
        int x = k.second;
        if(vis[x])  continue;
        vis[x] = 1;
        for(int e = fir[x];e != -1;e = next[e]) {
            if(d[s][v[e]] > d[s][x] + w[e]) {
               d[s][v[e]] = d[s][x] + w[e];
               q.push(make_pair(d[s][v[e]],v[e]));
            }
        }
    }
}

int main() {
    int m,p;
    memset(fir,-1,sizeof(fir));
    scanf("%d%d%d",&n,&m,&p);
    ind = 0;
    while(m--) {
        int f,t,val;
        scanf("%d%d%d",&f,&t,&val);
        add_edge(f,t,val);
    }

    for(int i = 1;i <= n;i++)   Dijstra(i);

    int max_time = -1;
    for(int i = 1;i <= n;i++) {
        if(i == p)  continue;
        if(max_time < d[i][p] + d[p][i])
           max_time = d[i][p] + d[p][i];
    }

    printf("%d
",max_time);
    return 0;
}