AOJ 0562 : Shopping in JOI Kingdom

問題リンク:Shopping in JOI Kingdom | Aizu Online Judge

問題概要：

使用した言語：C++

解法：
ノードがMAX３０００個なのでpriority_queueを使ってDijkstraをした
最初priority_queueにはスタート地点として全てのショッピングモールをもつ町を入れる
ショッピングモールから各ノードへの最短経路を求めたらループを回してもっとも遠い距離をさがす
もっとも遠い距離はショッピングモール、そうでない2点からなる3角形の周を２で割ったもの

ちなみにグラフの情報をvectorのほかにmapでも保存していたらMLEをくらった

コード：

#include<iostream>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<stack>
#define F first
#define S second

using namespace std;
typedef pair<int,int> P;
typedef vector<P> VP;
typedef vector<int> VI;
typedef vector<VP> VVP;
typedef vector<VI> VVI;
class Pox
{
public:
  int cost,now;
  Pox():cost(0),now(0){}
  Pox(int now,int cost):now(now),cost(cost){}
};

class ope{
public:
  bool operator() (Pox a,Pox b)
  {
    return a.cost > b.cost;
  }
};

const int INF = (1<<28);
int N,M,K;
VVP G;
VI mincost;
//map<P,int> D;

int main()
{
  scanf("%d %d %d",&N,&M,&K);
  G.resize(N),mincost.resize(N);
  for(int i=0;i<N;i++)
      mincost[i] = INF;

  for(int i=0;i<M;i++)
    {
      int a,b,c;
      scanf("%d %d %d",&a,&b,&c);
      a--,b--;
      G[a].push_back(P(b,c));
      G[b].push_back(P(a,c));
      //D[P(a,b)] = D[P(b,a)] = c;
    }

  priority_queue<Pox,vector<Pox>,ope> Q;
  for(int i=0;i<K;i++)
    {
      int a;
      scanf("%d",&a);
      a--;
      Q.push(Pox(a,0));
      mincost[a] = 0;
    }

  while(!Q.empty())
    {
      Pox pox = Q.top(); Q.pop();
      int now = pox.now;
      int total = pox.cost;

      for(int i=0;i<G[now].size();i++)
	{     
	  P p = G[now][i];
	  int to = p.F;
	  int cost = p.S;
	  if(mincost[to] <= total + cost)
	    continue;

	  mincost[to] = total + cost;
	  Q.push(Pox(to,total+cost));
	}
    }


  double mex = 0;
 for(int i=0;i<N;i++)
    for(int j=0;j<G[i].size();j++)
	if(j != i && mincost[G[i][j].F] != INF && mincost[i] != INF/* && D[P(i,j)]*/)
	  mex = max(mex,(double)(mincost[i]+mincost[G[i][j].F]+G[i][j].S/*D[P(i,j)]*/)/2.0 );

  cout << round(mex) << endl;

  return 0;
}