POJ3268 Silver Cow Party

POJ3268

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int T, N, M, Q, dp[100005], dp1[100005];
vector<pair<int, pair<int, int> > > node[100005];
void ini(void){
  int i, j, k, c;
  scanf("%d %d %d", &N, &M, &Q);
  for(i = 0; i < M; i++){
    scanf("%d %d %d", &j, &k, &c);
    
    // 1 表正向， 0 為反向
    node[j].push_back(make_pair(1, make_pair(k, c)));
    node[k].push_back(make_pair(0, make_pair(j, c)));
  }
}

void sol(void){
  int i, j;
  
  //小到大，路徑和、index
  priority_queue<pair<int, int> , vector<pair<int, int> >, greater< pair<int, int> > > pq;
  pair<int, int> pii;

  memset(dp, 127, sizeof(dp));
  memset(dp1, 127, sizeof(dp));
  
  dp[Q] = 0;
  dp1[Q] = 0;

  pq.push(make_pair(0, Q));
  while(!pq.empty()){
    pii = pq.top();
    pq.pop();
    
    //因dij特性，寫第一次的值必定是到該點之最小路徑和
    if(dp[pii.second] <= pii.first) continue;
    dp[pii.second] = pii.first;

    for(i = 0, j = pii.second; i < node[j].size(); i++){
    
    	//只拿正向
      if(node[j][i].first && dp[node[j][i].second.first] > node[j][i].second.second + pii.first)
        pq.push(make_pair(node[j][i].second.second + pii.first, node[j][i].second.first));
    }
  }

  pq.push(make_pair(0, Q));
  while(!pq.empty()){
    pii = pq.top();
    pq.pop();
    
    //因dij特性，寫第一次的值必定是到該點之最小路徑和
    if(dp1[pii.second] <= pii.first) continue;
    dp1[pii.second] = pii.first;

    for(i = 0, j = pii.second; i < node[j].size(); i++){
    
    	//只拿反向
      if(!node[j][i].first && dp1[node[j][i].second.first] > node[j][i].second.second + pii.first)
        pq.push(make_pair(node[j][i].second.second + pii.first, node[j][i].second.first));
    }
  }
  
  //正向 + 反向之最大值
  for(i = 1, j = 0; i <= N; i++){
    j = max(dp[i] + dp1[i], j);
  }
  
  printf("%d\n", j);
}

int main(void){
  int i, j;

  ini();

  sol();

}