九度oj 题目1100：最短路径

题目描述：: 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 的结果输出。

样例输入：

样例输出：

8
9
11
这道题考了最短路径算法和大数运算，好歹做出来了

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cstring>
  4 #include <string>
  5 #include <cmath>
  6 #include <algorithm>
  7 
  8 #define MAX 102
  9 #define TENLEN 200
 10 #define modN 100000
 11 using namespace std;
 12 
 13 int flag[MAX];
 14 int k2[TENLEN];
 15 int minDis[TENLEN];
 16 int dis[TENLEN];
 17 
 18 struct Node
 19 {
 20     int dis[TENLEN];
 21     int zhi;
 22 };
 23 
 24 int graph[MAX][MAX];
 25 Node map[MAX][MAX];
 26 Node lowCost[MAX];
 27 
 28 void calSum(int sum[], int a[], int b[]) {
 29     int ci = 0;
 30     for(int i = 0; i < TENLEN;i++) {
 31         int ben = (a[i] + b[i] + ci) % 10;
 32         ci = (a[i] + b[i] + ci)/10;
 33         sum[i] = ben;
 34    } 
 35 }
 36 
 37 int cmp(int a[], int b[]) {
 38     for(int i = TENLEN-1; i >= 0; i--) {
 39         if(b[i] > a[i]) {
 40             return -1;
 41         }
 42         else if(a[i] > b[i]) {
 43             return 1;
 44         }
 45     }
 46     return 0;
 47 }
 48 
 49 int copy(int a[], int b[]) {
 50     for(int i = 0; i < TENLEN; i++) {
 51         b[i] = a[i];
 52     }
 53 }
 54 
 55 
 56 void modNprint(int a[]) {
 57     bool isBegin = false;
 58     for(int i = 4; i >= 0; i--) {
 59         if(!isBegin && a[i] != 0) {
 60             isBegin = true;
 61             printf("%d", a[i]);
 62         }
 63         else if(isBegin){
 64             printf("%d", a[i]);
 65         }
 66     }
 67     if(!isBegin) {
 68         printf("0");
 69     }
 70     printf("
");
 71 }
 72 
 73 void print(int a[]) {
 74     bool isBegin = false;
 75     for(int i = TENLEN - 1; i >= 0; i--) {
 76         if(!isBegin && a[i] != 0) {
 77             isBegin = true;
 78             printf("%d", a[i]);
 79         }
 80         else if(isBegin){
 81             printf("%d", a[i]);
 82         }
 83     }
 84     if(!isBegin) {
 85         printf("0");
 86     }
 87     printf("
");
 88 }
 89 int main(int argc, char const *argv[])
 90 {
 91     int n, m;
 92     //freopen("input.txt","r",stdin);
 93     while(scanf("%d %d",&n,&m) != EOF) {
 94         memset(k2, 0, sizeof(k2));
 95         k2[0] = 1;
 96         for(int i = 0; i < n; i++) { 
 97             for(int j = 0; j < n; j++) {
 98                 graph[i][j] = 0;
 99             }
100         }
101         for(int i = 0; i < m; i++) {
102             int atemp, btemp;
103             scanf("%d %d",&atemp,&btemp);
104             copy(k2, map[atemp][btemp].dis);
105             copy(k2, map[btemp][atemp].dis);
106             graph[atemp][btemp] = 1;
107             graph[btemp][atemp] = 1;
108             calSum(k2, k2, k2);
109             //print(k2);
110         }
111 
112         memset(flag, 0, sizeof(flag));
113         flag[0] = 1;
114         for(int i = 0; i < n; i++) {
115             if(graph[0][i] == 1) {
116                 copy(map[0][i].dis,lowCost[i].dis);
117             }
118         }
119 
120             
121         for(int i = 1; i < n; i++) {
122             for(int j = 0; j < TENLEN; j++) {
123                 minDis[j] = 9;
124             }
125             int min = -1;
126 
127             for(int j = 1; j < n; j++) {
128                 if(flag[j] == 0 && graph[0][j] == 1) {
129                     
130                     if(cmp(minDis, lowCost[j].dis) == 1) {
131                         copy(lowCost[j].dis,minDis);
132                         //print(minDis);
133                         //print(lowCost[j].dis);
134                         min = j;
135                     }
136                 }
137             }
138             //printf("min is %d
",min);
139             if(min != -1) {
140                 flag[min] = 1;
141                 for(int j = 0; j < n; j++) {
142                     if(flag[j] == 0 && graph[min][j] == 1 ) {
143                         calSum(dis, lowCost[min].dis, map[min][j].dis);
144                        if(graph[0][j] == 0 || cmp(dis,lowCost[j].dis) == -1) {
145                             graph[0][j] = 1;
146                             copy(dis,lowCost[j].dis);
147                         }
148                     }
149                     
150                 }
151             }
152         }
153         for(int i = 1; i < n; i++) {
154             if(graph[0][i] == 1) {
155                 modNprint(lowCost[i].dis);
156             }
157             else {
158                 puts("-1");
159             }
160             
161         }
162     }
163     return 0;
164 }

占用的内存略大，还需要再精简