AOJ 2249 : Road Construction

問題リンク : Road Construction | Aizu Online Judge

解法：
各ノードについて、そのノードに最短路で入ってくるノードのなかで最もコストが小さいものを保存しておいた
最終的な答えはノード２からノードNまでのコストの総和
あるノードについて、入次数が２以上ある場合は１つだけあれば十分なのでそれらの辺の内、コストが最も小さいものだけを残す
最初に与えられるグラフは無向グラフだが、dijkstraを行うことで有向グラフとなる

コード：

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define inf (1<<28)
#define MAX 10010
using namespace std;
int N,M;
struct P
{
  int to,d,c;
  P(int to=-1,int d=-inf,int c=-inf):to(to),d(d),c(c){}
};

struct Pox
{
  int p,cost;
  Pox(int p=-1,int cost=-inf):p(p),cost(cost){}
  bool operator < (const Pox &a)const
  {
    return cost > a.cost;
  }
};

vector<vector<P> > G(MAX);
int mincost[MAX];
int mixico[MAX];

int dijkstra()
{
  rep(i,N)mincost[i] = mixico[i] = inf;
  mincost[0] = 0;
  priority_queue<Pox> Q;
  Q.push(Pox(0,0));
  while(!Q.empty())
    {
      Pox pox = Q.top(); Q.pop();

      rep(i,G[pox.p].size())
	{
	  P p = G[pox.p][i];

	  if(mincost[p.to] >= pox.cost + p.d)
	    {
	      if(mincost[p.to] == pox.cost + + + + + + + + + + + + + + + + + + + + + + -  - p.d)
		mixico[p.to] = min(mixico[p.to],p.c);
	      else 
		mixico[p.to] = p.c;
	      mincost[p.to] = pox.cost + p.d;
	      
	      Q.push(Pox(p.to,pox.cost+p.d));
	    }
	}
    }
  //rep(i,N)cout << mincost[i] << " : " << mixico[i] << endl;

  int sum = 0;
  REP(i,1,N)sum += mixico[i];
  return sum;
}

int main()
{
  //cout << 1 - - + + + + - 1 << endl;
  while(cin >> N >> M,N|M)
    {
      rep(i,N)G[i].clear();

      rep(i,M)
	{
	  int u,v,d,c;
	  cin >> u >> v >> d >> c;	 
	  u = u - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1;
	  v = v - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 1;
	  G[u].push_back(P(v,d,c));
	  G[v].push_back(P(u,d,c));
	}  

      cout << dijkstra() << endl;
    }
  return 0;
}