1525 - 最短路径2
时间限制 : 1 秒
内存限制 : 32 MB
N个城市，标号从0到N-1，M条道路，第K条道路（K从0开始）的长度为2^K，求编号为0的城市到其他城市的最短距离。
题目输入
第一行两个正整数N（2<=N<=100）M(M<=500),表示有N个城市，M条道路，
接下来M行两个整数，表示相连的两个城市的编号。
题目输出
N-1行，表示0号城市到其他城市的最短路，如果无法到达，输出-1，数值太大的以MOD 100000 的结果输出。
输入/输出样例
输入格式
4 3 0 1 1 2 2 0
输出格式
1 3 -1
C语言解答
#include<stdio.h> const int inf=1000000000; const int mod=100000; int p[101],rank[101],d[101][101]; int Find(int i) { if(i==p[i]) return i; else { p[i]=Find(p[i]); return p[i]; } } void Union(int a,int b) { int ta=Find(a),tb=Find(b); if(ta==tb) return; if(rank[a]>=rank[b]) { p[tb]=ta; rank[ta]+=rank[tb]; } else { p[ta]=tb; rank[tb]+=rank[ta]; } } int Pow( long a,long b) { long ret=1; while(b>0) { if(b&1) ret=(ret*a)%mod; b>>=1; a=(a*a)%mod; } return ret; } int main() { int n,m,i,j,k,a,b,ta,tb,dist; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) { p[i]=i; rank[i]=1; d[i][i]=0; } for(k=0;k<m;k++) { scanf("%d%d",&a,&b); ta=Find(a); tb=Find(b); if(ta==tb) continue; dist=Pow(2,k); for(i=0;i<n;i++) { if(Find(i)!=ta) continue; for(j=0;j<n;j++) { if(Find(j)!=tb) continue; d[i][j]=(d[i][a]+dist+d[b][j])%mod; d[j][i]=d[i][j]; } } Union(a,b); } ta=Find(0); for(i=1;i<n;i++) { if(Find(i)==ta) printf("%d\n",d[0][i]); else printf("-1\n"); } } return 0; }
C++解答
#include<stdio.h> const int inf=1000000000; const int mod=100000; int p[101],rank[101],d[101][101]; int Find(int i) { return i==p[i]?i:p[i]=Find(p[i]); } void Union(int a,int b) { int ta=Find(a),tb=Find(b); if(ta==tb) return; if(rank[a]>=rank[b]) { p[tb]=ta; rank[ta]+=rank[tb]; } else { p[ta]=tb; rank[tb]+=rank[ta]; } } int Pow(long long a,long long b) { long long ret=1; while(b>0) { if(b&1) ret=(ret*a)%mod; b>>=1; a=(a*a)%mod; } return ret; } int main() { int n,m,i,j,k,a,b,ta,tb,dist; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) { p[i]=i; rank[i]=1; d[i][i]=0; } for(k=0;k<m;k++) { scanf("%d%d",&a,&b); ta=Find(a); tb=Find(b); if(ta==tb) continue; dist=Pow(2,k); for(i=0;i<n;i++) { if(Find(i)!=ta) continue; for(j=0;j<n;j++) { if(Find(j)!=tb) continue; d[i][j]=(d[i][a]+dist+d[b][j])%mod; d[j][i]=d[i][j]; } } Union(a,b); } ta=Find(0); for(i=1;i<n;i++) { if(Find(i)==ta) printf("%d\n",d[0][i]); else printf("-1\n"); } } return 0; }
Java解答
import java.math.BigDecimal; import java.math.BigInteger; import java.util.Scanner; public class Main { final static BigDecimal INF = new BigDecimal(2).pow(10002); public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int N = scanner.nextInt(); int M = scanner.nextInt(); BigDecimal[][] matrix = new BigDecimal[N][N]; boolean[] visit = new boolean[N]; BigDecimal[] dis = new BigDecimal[N]; // initial for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) matrix[i][j] = INF; for (int i = 0; i < N; i++) matrix[i][i] = new BigDecimal(0); for (int i = 0; i < N; i++) visit[i] = false; // assignment for (int i = 0; i < M; i++) { int a = scanner.nextInt(); int b = scanner.nextInt(); if (matrix[a][b] == INF) { //注意：同一条边不能重复赋值 BigDecimal weight = new BigDecimal(2).pow(i); matrix[b][a] = matrix[a][b] = weight; } } for (int i = 0; i < N; i++) dis[i] = matrix[0][i]; // shortest path int next = 0; visit[0] = true; for (int i = 1; i < N; i++) { // repeat N-1 times for (int j = 1; j < N; j++) { if (!visit[j]) { if (dis[j].compareTo(dis[next].add(matrix[next][j])) > 0) dis[j] = dis[next].add(matrix[next][j]); } } BigDecimal min = INF; for (int j = 1; j < N; j++) { if (!visit[j]) { if (dis[j].compareTo(min) < 0) { min = dis[j]; next = j; } } } visit[next] = true; } for (int i = 1; i < N; i++) { if (dis[i].compareTo(INF) < 0) System.out.println(dis[i].toBigInteger().mod(new BigInteger("100000"))); else System.out.println(-1); } } scanner.close(); } }