「AOJ Problem Set from ALDS1 問35～39」の編集履歴（バックアップ）一覧はこちら

「AOJ Problem Set from ALDS1 問35～39」(2014/01/23 (木) 21:57:50) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*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 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;
 }