首页 > 代码库 > JOBDU 题目1100:最短路径
JOBDU 题目1100:最短路径
时间限制:1 秒
内存限制:32 兆
特殊判题:否
提交:5786
解决:902
- 题目描述:
-
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 4 1 2 2 3 1 3 0 1
- 样例输出:
-
8 9 11
并查集+Floyd。
并查集判断是否连通。
//Asimple //#include <bits/stdc++.h> #include <iostream> #include <sstream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <cctype> #include <cstdlib> #include <stack> #include <cmath> #include <set> #include <map> #include <string> #include <queue> #include <limits.h> #include <time.h> #define INF 0xfffffff #define mod 100000 #define PI 3.14159265358979323 #define swap(a,b,t) t = a, a = b, b = t #define CLS(a, v) memset(a, v, sizeof(a)) #define debug(a) cout << #a << " = " << a <<endl #define dobug(a, b) cout << #a << " = " << a << " " << #b << " = " << b << endl using namespace std; typedef long long ll; const int maxn = 101; int n, m, num, T, k, len, ans, sum, x, y; int Map[maxn][maxn]; int fa[maxn]; ll qpow(ll a, ll b, ll md) { ll ans = 1; while( b ) { if( b & 1 ) ans = ans * a % md; a = a * a % md; b = b >> 1; } return ans; } int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } void solve() { x = find(0); for(int i=1; i<n; i++) { if( x!=find(i) ) cout << "-1" << endl; else cout << Map[0][i] << endl; } } void input() { while( cin >> n >> m ) { for(int i=0; i<n; i++) { fa[i] = i; Map[i][i] = 0; } for(int i=0; i<m; i++) { cin >> x >> y; num = qpow(2, i, mod); int xx = find(x); int xy = find(y); if( xx==xy ) continue; for(int j=0; j<n; j++) { if( xx!=find(j) ) continue; for(int k=0; k<n; k++) { if( xy!=find(k) ) continue; Map[j][k] = Map[k][j] = (Map[j][x] + num + Map[y][k])%mod; } } fa[xy] = xx; } solve(); } } int main(){ input(); return 0; }
JOBDU 题目1100:最短路径
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。