#include<iostream> #include<string> using namespace std; //本题坑点:会重复输入边,本题以第一次输入为准,切忌覆盖 //方法:高精度运算和弗洛伊德 //注意:是无向图 //高精度乘法 //999999999999999999999*2 string mul(string s, int a) { string res = ""; int carry = 0; res = s; for (int i = s.length()-1; i >= 0; i--) { res[i] = ((s[i] - '0') * a + carry) % 10+'0'; carry = ((s[i] - '0') * a + carry) / 10; } if (carry > 0) { res.insert(0, 1, carry + '0'); } return res; } //高精度加法 string add(string a, string b) { string res = ""; int d = a.length() - b.length(); if (d > 0) { b.insert(0, d, '0'); } else if(d<0) { a.insert(0, -d, '0'); } res = a; int carry = 0;//进位 for (int i = a.length() - 1; i >= 0; i--) { res[i] = char((a[i] - '0' + b[i] - '0' + carry) % 10+'0'); carry = (a[i] - '0' + b[i] - '0' + carry) / 10; } if (carry > 0) res.insert(0, 1, carry + '0'); return res; } //比大小(不是字符串大小,而是字符串代表的整数的大小) //a>b返回true bool isgreater(string a, string b) { if (a.length() > b.length()) return true; else if (a.length() < b.length()) return false; else { for (int i = 0; i < a.length(); i++) { if (a[i] > b[i]) return true; if (a[i] < b[i])return false; if (a[i] == b[i])continue; } } return false; } int main() { //string s1 = "88888"; //string s2 = "22"; ////测试高精度乘法 //cout<<mul(s1, 2)<<endl; ////测试高精度加法 //cout << add(s1, s2); int cities, roads; int from, to; //初始化图 string g[100][100]; for (int i = 0; i < 100; i++) for (int j = 0; j < 100; j++) g[i][j] = "INF";//表示此路不通 while(cin >> cities >> roads) { //输入边 string s="1";//第一条边的距离是1 for (int i = 0; i < roads; i++) { cin >> from >> to; if (i!= 0) { s = mul(s, 2); } if(g[from][to]=="INF")//之所以加这个是因为会有重复输入,题目以第一次输入为准 g[from][to]= g[to][from] = s; } } //开始弗洛伊德 for (int k = 0; k < cities; k++) { for (int i = 0; i < cities; i++) { for (int j = 0; j < cities; j++) { if(i==j) continue; if (g[i][k] == "INF" || g[k][j] == "INF") continue; if (g[i][j] == "INF"||isgreater(g[i][j], add(g[i][k], g[k][j]))) { g[i][j]= add(g[i][k], g[k][j]); } } } } //处理输出 for (int i = 1; i < cities; i++) { if (g[0][i] == "INF") cout << "-1" << endl; else if (g[0][i].length() > 5) cout << stoi(g[0][i].substr(g[0][i].length() - 5)) << endl; else cout << stoi(g[0][i]) << endl; } }