AOJ Problem Set from ALDS1 問35～39 - c21coterie @ ウィキ

Graph II - Single Source Shortest Path I

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B
ダイクストラ法を実装せよという問題。
データ量が小さいのでまあ手抜きで書きました。

#include<stdio.h>

static const int MAX = 500;
static const int INFTY = (1<<21);

main(){
 int n, i, j,u,v,c,k;
 int d[MAX],M[MAX][MAX];

 scanf("%d", &n);
 for ( i = 0; i< n; i++ ){
   d[i]=INFTY;
   for ( j = 0; j < n; j++ ){
     M[i][j] = INFTY;
   }
 }  
 for ( i = 0; i < n; i++ ){
   scanf("%d %d", &u, &k);
   for ( j = 0; j < k; j++ ){
     scanf("%d %d", &v, &c);
     M[u][v] = c;
   }
 }
 d[0]=0;
  for(int i=0;i<n;i++){
 	for(int nowP=0;nowP<n;nowP++){
		if(d[nowP]==INFTY)continue;
		for(int e=0;e<n;e++){
 			int g=d[nowP]+M[nowP][e];
			if(d[e]>g)d[e]=g;
		}
	}
 }
 
 for ( i = 0; i < n; i++ ){
   printf("%d %d\n", i, (d[i]==INFTY?-1:d[i]));
 }

 return 0;
}

Graph II - Single Source Shortest Path II

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C
ミドルサイズデータでダイクストラ法を実装せよという問題

#include<stdio.h>
#include<vector>
#include<queue>

static const int MAX = 10000;
static const int INFTY = 10000*10000*10+1;

struct E{
	int v,c;
	bool operator<(const E& e)const{
		return c>e.c;
	}
};

main(){
 int n, i, j,u,v,c,k;
 int d[MAX];
 std::vector<E> M[MAX];
 E e1,e2;
 std::priority_queue<E> pq;
 scanf("%d", &n);
 for ( i = 0; i< n; i++ ){
   d[i]=INFTY;
 }
 
 for ( i = 0; i < n; i++ ){
   scanf("%d %d", &u, &k);
   for ( j = 0; j < k; j++ ){
     scanf("%d %d", &e1.v, &e1.c);
     M[u].push_back(e1);
   }
 }
 d[0]=0;
 for(int i=0;i<M[0].size();i++){
 	pq.push(M[0][i]);
 }
 
  while(pq.empty()==false){
 	e1=pq.top();
	pq.pop();
	if(d[e1.v]!=INFTY)continue;
	d[e1.v]=e1.c;
	for(int i=0;i<M[e1.v].size();i++){
 		e2=M[e1.v][i];
		e2.c+=e1.c;
		if(e2.c>=d[e2.v])continue;
		pq.push(e2);
	}
 }
 
  for ( i = 0; i < n; i++ ){
    printf("%d %d\n", i, (d[i]==INFTY?-1:d[i]));
   }

  return 0;
}