第一行两个正整数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
最短路径:迪杰斯特拉 大整数:使用字符串存储长度与快速幂取模来模拟
#include<iostream> (720)#include<algorithm> #include<queue> (789)#include<string> #include<vector> using namespace std; const int N = 300; struct Edge { int end; string length; bool operator < (Edge c) const { return length < c.length; } }; struct Point { int pointnumber; string distance; Point(int a, string b) : pointnumber(a), distance(b) {} bool operator<(Point c)const { return distance > c.distance; } }; string dist[N]; //源点到其他点的距离 int cost[N]; priority_queue<Point> mindis; //用于筛选最短距离的点 string chart(int k) // 2的k次方 { string s; s.insert(0, 502, '0'); s[s.size()-1-k] = '1'; return s; } string adds(string a, string b) //字符串加法 { string s; for (int i = 0; i < a.size(); i++) s.append(1, (a[i] - '0' + b[i] - '0')+'0'); return s; } int atois(string s) //快速幂取模 { int ans=0; int front = 1; for (int i = s.size()-1; i>=0; i--) { if (s[i] == '1') { ans += front; ans = ans % 100000; } front = (front * 2) % 100000; } return ans; } void Dijkstra(int z,vector<Edge>graph[N]) //最短路径 { dist[z][0] = '0'; mindis.push(Point(z,dist[z])); while (!mindis.empty()) { int k = mindis.top().pointnumber; mindis.pop(); for (int i =0 ; i < graph[k].size(); i++) { string old = dist[graph[k][i].end]; string news = adds(dist[k] , graph[k][i].length); if (old > news ) { dist[graph[k][i].end] = news; mindis.push(Point(graph[k][i].end, dist[graph[k][i].end])); } } } } void Initial() { for (int i = 0; i < N; i++) { dist[i] = chart(501); } dist[0][0] = '0'; } int main() { int n, m; int a, b; while (cin>>n>>m) { Initial(); vector<Edge> graph[N]; for (int i = 0; i < m; i++) { Edge x; cin >> a>>b; x.end = b; x.length = chart(i); graph[a].push_back(x); x.end = a; graph[b].push_back(x); } Dijkstra(0, graph); for (int i = 1; i < n; i++) { if (dist[i] == chart(501)) cout << "-1" << endl; else cout << atois(dist[i])<<endl; } } }
//AC代码: import java.math.*; import java.util.*; public class Main { static String INF=""; static BigInteger [][]G=new BigInteger[105][105]; static BigInteger MOD=new BigInteger("100000"),Base=new BigInteger("2"); public static void main(String [] args){ int n,m,i,j,k,a,b; for(i=0;i<160;i++) INF+="9"; for(i=0;i<105;i++) for(j=0;j<105;j++) if(i!=j) G[i][j]=new BigInteger(INF); else G[i][j]=new BigInteger("0"); Scanner in=new Scanner(System.in); n=in.nextInt(); m=in.nextInt(); for(k=0;k<m;k++){ a=in.nextInt(); b=in.nextInt(); if(!G[a][b].toString().equals(INF)) continue; G[a][b]=new BigInteger(Base.pow(k).toString()); G[b][a]=new BigInteger(Base.pow(k).toString()); } for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(G[i][j].compareTo(G[i][k].add(G[k][j]))>0) G[i][j]=G[i][k].add(G[k][j]); for(i=1;i<n;i++) if(G[0][i].toString().equals(INF)) System.out.println("-1"); else System.out.println(G[0][i].mod(MOD)); } }//100个点 直接弗洛伊德就能AC
using namespace std; #include <cstdio> #include <vector> #include <queue> #include <iostream> #include <utility> int par[110], Rank[110], dis[110], vis[110]; int n, m; struct edge{ int to; int l; edge(int tt, int ll):to(tt), l(ll){} }; vector<edge> graph[110]; void init(){ for(int i(0);i<=n;++i){ par[i] = i; Rank[i] = 1; dis[i] = -1; vis[i] = 0; } } int find(int n){ if(n == par[n])return n; else return find(par[n]); } void unite(int x, int y){ x = find(x), y = find(y); if(x == y)return; if(Rank[x] <= Rank[y])par[x] = y; else par[y] = x; if(Rank[x] == Rank[y])++Rank[x]; } int main(){ while(scanf("%d%d", &n, &m) != EOF){ int len = 1; int x, y; init(); for(int i(0);i<m;++i){ scanf("%d%d", &x, &y); if(find(x) != find(y)){ unite(x, y); graph[x].push_back(edge(y, len)); graph[y].push_back(edge(x, len)); } len = (len * 2)%100000; } queue< pair<int, int> > q; q.push(make_pair(0, 0)); vis[0] = 1; while(!q.empty()){ int u = q.front().first; int d = q.front().second; q.pop(); for(int i(0);i<graph[u].size();++i){ int v = graph[u][i].to; int dd = graph[u][i].l; if(vis[v] == 0){ dis[v] = (d + dd)%100000; q.push(make_pair(v, dis[v])); vis[v] = 1; } } } for(int i(1);i<n;++i)printf("%d\n", dis[i]); } return 0; }
//天坑,这题有重复输入,检测到第二次输入时,不应该向图中添加路径 //用并查集的板子来解决重复输入的问题,两个结点已经是联通的,就不要再继续覆盖路径了 #include <iostream> (720)#include <vector> #include <queue> (789)#include <algorithm>//包含fill函数 #include <cstring>//包含memset函数 (2978)#include <climits>//包含INT_MAX using namespace std; const int MAXN = 101; const int INF = INT_MAX; struct Edge//源点即为下标 { int to;//终点下标 int length;//路径长度 Edge(int t, int l) : to(t),length(l) {} }; struct Point { int num;//点的编号 int dist;//源点到该点的距离 Point(int n, int d) : num(n),dist(d) {} bool operator< (const Point& p) const { return dist > p.dist;//优先队列输出的是最大的那个,距离越近的优先级应该越高 } }; vector<Edge> graph[MAXN];//存储图,graph[i]存储以i为出发结点的所有边 int dis[MAXN];//存储所有结点到目标结点的距离 int father[MAXN]; int height[MAXN]; void initial(int n) { for(int i=0; i<n; i++) { father[i] = i; height[i] = 0; } } int findroot(int x) { if(x != father[x]) { father[x] = findroot(father[x]); } return father[x]; } void Union(int x, int y) { int a = findroot(x); int b = findroot(y); if(a != b) { if(height[a] > height[b]) { father[b] = a; } else if(height[a] < height[b]) { father[a] = b; } else { father[b] = a; height[a] ++; } } return ; } void dijkstra(int s)//输入起点下标 { priority_queue<Point> q;//优先级队列 dis[s] = 0; q.push(Point(s,dis[s]));//入队 while(!q.empty())//队列不空时 { int u = q.top().num;//距离源点最近的点的编号 q.pop();//队首元素出队 for(int i=0; i<graph[u].size(); i++)//遍历以u为头结点的所有边 { int v = graph[u][i].to;//当前边的终点 int d = graph[u][i].length;//u到v的距离 if(dis[v] > dis[u]+d)//松弛操作,发现距离更近的一条路时,更新路径 { dis[v] = dis[u]+d; q.push(Point(v,dis[v]));//将更新后的结点入队 } } } } int main() { int n,m; while(cin >> n >> m) { initial(n); fill(dis,dis+n,INF);//初始化距离函数 memset(graph,0,sizeof(graph));//图初始化 int length = 1; for(int i=0; i<m; i++) { int from,to; cin >> from >> to; if(findroot(from) != findroot(to)) { graph[from].push_back(Edge(to,length));//向图内存储路径 graph[to].push_back(Edge(from,length)); Union(from,to); } length = length*2%100000; } dijkstra(0); for(int i=1; i<n; i++) { if(dis[i] == INF) cout << "-1" << endl; else cout << dis[i]%100000 << endl; } } return 0; }
#include<bits/stdc++.h> using namespace std; const int maxlen = 1e3; const int maxn = 1e2; struct Bign //大整数 { int d[maxlen+5], len; Bign() { fill(d, d+maxlen, 0); len = 0; } }; Bign INF; vector<pair<int, Bign> > G[maxn+5]; //图的邻接表 Bign d[maxn+5]; bool inq[maxn+5]; int num[maxn+5]; int n, m; int cmpNumber(Bign n1, Bign n2) //大整数比较 { if(n1.len > n2.len) return 1; else if(n1.len < n2.len) return -1; else { for(int i = n1.len-1;i >= 0; i--) { if(n1.d[i] > n2.d[i]) return 1; else if(n1.d[i] < n2.d[i]) return -1; } return 0; } } Bign Add(Bign n1, Bign n2) //大整数加法 { Bign n3; int c = 0; for(int i = 0;i < n1.len || i < n2.len; i++) { int t = n1.d[i]+n2.d[i]+c; n3.d[n3.len++] = t%10; c = t/10; } if(c) n3.d[n3.len++] = c; return n3; } Bign Mul(Bign n1, Bign n2) //大整数乘法 { Bign n3; for(int i = 0;i < n1.len; i++) { for(int j = 0;j < n2.len; j++) n3.d[i+j] += n1.d[i]*n2.d[j]; } n3.len = n1.len+n2.len-1; int c = 0; for(int i = 0;i < n3.len; i++) { int t = n3.d[i]+c; n3.d[i] = t%10; c = t/10; } while(c) { n3.d[n3.len++] = c%10; c /= 10; } return n3; } Bign Div(Bign n1, int n2, int& r) //大整数除法 { Bign n3; n3.len = n1.len; r = 0; for(int i = n1.len-1;i >= 0; i--) { r = r*10+n1.d[i]; if(r < n2) n3.d[i] = 0; else { n3.d[i] = r/n2; r %= n2; } } while(n3.len > 1 && n3.d[n3.len-1] == 0) n3.len--; return n3; } Bign getPow2K(int k) //大整数2的k次幂 { Bign ans; ans.d[ans.len++] = 1; Bign t; t.d[t.len++] = 2; for(int i = 0;i < k; i++) { ans = Mul(ans, t); } return ans; } void InitialINF() //大整数无穷大初始化 { INF.len = 500; fill(INF.d, INF.d+INF.len, 9); } void Create() //创建图 { int u, v; for(int i = 0;i < m; i++) { cin >> u >> v; Bign w = getPow2K(i); G[u].push_back(make_pair(v, w)); G[v].push_back(make_pair(u, w)); } } bool PSFA() //PSFA求解单源最短路(若数据多可以用SLF优化) { InitialINF(); fill(d, d+maxn, INF); fill(num, num+maxn, 0); fill(inq, inq+maxn, false); Bign zero; zero.d[zero.len++] = 0; queue<int> q; q.push(0); inq[0] = true; num[0]++; d[0] = zero; while(!q.empty()) { int u = q.front(); q.pop(); inq[u] = false; for(int i = 0;i < G[u].size(); i++) { int v = G[u][i].first; Bign dis = G[u][i].second; if(cmpNumber(Add(d[u], dis), d[v]) == -1) { d[v] = Add(d[u], dis); if(!inq[v]) { q.push(v); inq[v] = true; num[v]++; if(num[v] >= n) return false; } } } } return true; } int main() { ios::sync_with_stdio(false); while(cin >> n >> m) { Create(); PSFA(); for(int i = 1;i < n; i++) { if(cmpNumber(d[i], INF) == 0) cout << -1 << "\n"; else { int r; Div(d[i], 100000, r); cout << r << "\n"; } } } return 0; }
#include <iostream> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cstring> #include <climits> #include <map> #include <queue> using namespace std; const int MAXN = 101; const int INF = INT_MAX; int dis[MAXN][MAXN]; //邻接矩阵 int father[MAXN]; //并查集父亲节点 int currentN; //当前路的数量,当为n-1时表示连通 int cost[MAXN]; //起点到各点的最小距离 bool visited[MAXN]; //bfs时使用 int n,m; //村庄数,道路数 struct point{ //bfs时使用 int num; //编号 int distance; //起点到本节点的距离 point(int n, int d):num(n), distance(d){} }; //中型快速幂 long long fastE(long long x, int y, int c){ long long ans =1; while(y!=0){ if(y%2==1){ ans *=x; ans%=c; } y/=2; x*=x; x%=c; } // cout<<ans<<endl; return ans; } int Find(int x){ if(father[x]!=x){ father[x] = Find(father[x]); } return father[x]; } void Union(int x, int y, int len){ int fax = Find(x); int fay = Find(y); if(fax!=fay){//两个点还没有连通,长度可以要 father[fay] = fax; dis[x][y] = len; dis[y][x] = len; currentN++; } } void bfs(){ queue<point>q; visited[0] = true; cost[0] = 0; q.push(point(0,0)); while(!q.empty()){ point p = q.front(); q.pop(); for(int i=0; i<n; i++){ if(!visited[i] && i!=p.num && dis[p.num][i]!=INF){//如果连通并且没访问过 visited[i] = true; cost[i] = (cost[p.num]+dis[p.num][i])%100000; q.push(point(i, cost[i])); } } } } int main(){ while(cin>>n>>m&&n&&m){ currentN = 0; //我们需要n-1条路构成最小生成树 //初始化 for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ dis[i][j] = INF; } dis[i][i]= 0; visited[i] = false; cost[i] = INF; father[i] = i; } int k=0; int p1,p2; int newDis; for(int i=0; i<m; i++){ cin>>p1>>p2; if(currentN==n-1){//已经连通了,后后面输入的数据直接跳过 continue; } newDis = fastE(2, k, 100000);//虽然fastE的返回是long long 但是由于取模了可以保证是在int范围内 // cout<<newDis<<endl; Union(p1, p2, newDis); k++; } bfs(); for(int i=1; i<n; i++){ if(!visited[i]) cout<<-1<<endl; else cout<<cost[i]<<endl; } } return 0; }
#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> using namespace std; const int MAXN = 105; struct enode { int to, EXP; enode(int t = -1, int e = -1) :to(t), EXP(e) {} }; vector<enode> graph[MAXN]; int tab[MAXN], dis[MAXN]; //并查集、距离数组 bool visited[MAXN]; void Initial(int n) { //每组数据初始化 memset(visited, false, sizeof(visited)); fill(dis, dis + n, 0); for (int i = 0; i < n; i++) { tab[i] = i; } } int convert(int base, int e, int mod) { //不采用快速幂的原因是e最大500,而快速幂避免上溢必须用long long,得不偿失 int ans = 1; for (int i = 0; i < e; i++) { ans = ans * 2 % 100000; } return ans; } int Find(int x) { return (x == tab[x]) ? x : Find(tab[x]); } bool Union(int x, int y) { //两个并查集的基本操作,这里就不加入高度了 x = Find(x), y = Find(y); if (x == y) return false; tab[y] = x; return true; } void BFS(int s, int n) { //BFS更新dis数组 dis[s] = 0; visited[s] = true; vector<int> sta; sta.push_back(s); while (!sta.empty()) { int p = sta.back(); sta.pop_back(); for (int i = 0; i < graph[p].size(); i++) { int t = graph[p][i].to; if (!visited[t]) { visited[t] = true; dis[t] = dis[p] + convert(2, graph[p][i].EXP, 100000); dis[t] %= 100000; //避免5e4 + 6e4这样超过mod sta.push_back(t); } } } } int main() { //根据读入顺序用Kruskal算法构建最小生成树,再BFS即可 int n, m, a, b; while (scanf("%d%d", &n, &m) != EOF) { Initial(n); for (int i = 0; i < m; i++) { scanf("%d%d", &a, &b); if (Union(a, b)) { graph[a].push_back(enode(b, i)); graph[b].push_back(enode(a, i)); } } BFS(0, n); for (int i = 1; i < n; i++) { if (visited[i]) printf("%d\n", dis[i]); else printf("-1"); } } return 0; }
#include<stdio.h> #define N 100 int dis[N][N]; int Tree[N]; int FindRoot(int x){ if(Tree[x]==-1) return x; else{ Tree[x]=FindRoot(Tree[x]); return Tree[x]; } } int mod(int x,int y){ int ret=1; while(y--){ ret=(ret*x)%100000; } return ret; } int main(){ int n,m; while(scanf("%d%d",&n,&m)!=EOF){ int i,j,k,a,b,x,y,dist; for(i=0;i<n;i++){ Tree[i]=-1; for(j=0;j<n;j++) dis[i][j]=-1; dis[i][i]=0; } for(i=0;i<m;i++){ scanf("%d%d",&a,&b); x=FindRoot(a); y=FindRoot(b); if(x!=y){ dist=mod(2,i); for(j=0;j<n;j++){ if(x==FindRoot(j)){ for(k=0;k<n;k++){ if(y==FindRoot(k)){ dis[j][k]=dis[k][j]=(dis[j][a]+dis[b][k]+dist)%100000; } } } } Tree[y]=x; } } x=FindRoot(0); for(i=1;i<n;i++){ printf("%d\n",dis[0][i]); } } return 0; }
#include<iostream>using namespace std;int root[105];int distances[105][105];//查找x的根节点int findRootOf(int x){if(root[x]==x)return x;else return root[x]=findRootOf(root[x]);}//计算第k条边的长度(已经mod100000的结果)int getEdgeDist(int k){int dist=1;while(k>0){dist=(dist*2)%100000;--k;}return dist;}int main(int argc, char const *argv[]){int vertexNum;while(cin>>vertexNum){int edgeNum;cin>>edgeNum;//初始化for(int i=0;i<vertexNum;++i){root[i]=i;for(int j=0;j<vertexNum;++j){distances[i][j]=-1;}distances[i][i]=0;}for(int k=0;k<edgeNum;++k){int edgePointA,edgePointB;cin>>edgePointA>>edgePointB;int rootOfPointA=findRootOf(edgePointA);int rootOfPointB=findRootOf(edgePointB);//如果AB已经在同一个集合里了//那么这条边的长度一定比当前AB距离的长度要长//故舍去,跳过此次松弛操作if(rootOfPointA==rootOfPointB)continue;int edgeDist=getEdgeDist(k);//计算当前这条边的长度;for(int i=0;i<vertexNum;++i){//i与A不在一个集合里?抱歉我们无法进行这次距离的更新if(rootOfPointA!=findRootOf(i))continue;for(int j=0;j<vertexNum;++j){//j与B不在一个集合里?抱歉我们也无法进行这次距离的更新if(rootOfPointB!=findRootOf(j))continue;distances[j][i]=distances[i][j]=(distances[i][edgePointA]+distances[edgePointB][j]+edgeDist)%100000;}}//A B原来不在同一个集合里,现在我们把它们连接起来root[rootOfPointB]=rootOfPointA;}for(int i=1;i<vertexNum;++i)cout<<distances[0][i]<<endl;}return 0;}
/*综合一下,有两种方法,第一种就是使用大整数+Dijkstra,第二种就是上面大神*/ /*提到的使用并查集的方法,如果两个点不属于一个集合,则合并这两个点*/ /*方法一:使用Dijkstra算法,只不过要用到与大数有关的计算*/ #include<cstdio> #include<iostream> #include<queue> #include<algorithm> #include<cstring> #define MAXN 100 using namespace std; struct Edge{ int to; /*边的一个顶点*/ string length; /*边长*/ Edge(int t, string l): to(t), length(l) {} }; struct Point{ int number; /*点编号*/ string distance; /*距离源点距离*/ Point(int n, string d): number(n), distance(d) {} bool operator<(const Point &p) const{ return distance>p.distance; /*因为下面用到优先级队列,优先级队列默认是大根堆,而我们要用的是小根堆,所以注意这里return是大于号*/ } }; vector<Edge> graph[MAXN]; /*使用邻接表存储图*/ string dis[MAXN]; /*距离源点的距离*/ string adds(string s1, string s2){ /*字符串加法*/ int carry=0, current; int i=s1.size()-1; int j=s2.size()-1; string ans; while(i>-1 && j>-1){ current=s1[i]-'0'+s2[j]-'0'+carry; carry=current/10; ans+=current%10+'0'; i--; j--; } while(i>-1){ current=s1[i]-'0'+carry; carry=current/10; ans+=current%10 + '0'; i--; } while(j>-1){ current=s2[j]-'0'+carry; carry=current/10; ans+=current%10+'0'; j--; } if(carry) /*加法还有进位要再加1*/ ans+="1"; reverse(ans.begin(),ans.end()); /*因为ans正好与正确结果相反,所以使用reverse函数对字符串进行求逆,头文件是algorithm*/ return ans; } string multiple(string s,int k){ /*字符串乘法*/ int carry=0; for(int i=s.size()-1;i>-1;i--){ int current=(s[i]-'0')*k+carry; s[i]=current%10+'0'; carry=current/10; } if(carry) s=to_string(carry)+s; return s; } int Divide(string s){ /*字符串除法用于求模*/ int remainder=0; for(int i=0;i<s.size();i++){ int current=10*remainder+s[i]-'0'; remainder=current%100000; s[i]=current/100000; } return remainder; } bool cmpString(string s1,string s2){ /*两个字符串数比较大小*/ if(s1.size()>s2.size()) return true; /*位数多则一定大*/ else if(s1.size()<s2.size()) return false; else{ for(int i=0;i<s1.size();i++){ if(s1[i]-'0'>s2[i]-'0') return true; else if(s1[i]-'0'<s2[i]-'0') return false; } } return false; /*两个数相等*/ } void Dijkstra(){ dis[0]="0"; priority_queue<Point> Q; /*使用优先级队列,方便找出距离源点最近的点*/ Q.push(Point(0,dis[0])); while(!Q.empty()){ int u=Q.top().number; Q.pop(); for(int i=0;i<graph[u].size();i++){ int v=graph[u][i].to; string d=graph[u][i].length; string l=adds(dis[u],d); if(cmpString(dis[v],l)){ dis[v]=l; Q.push(Point(v,dis[v])); } } } return ; } int main(){ int n, m, a, b; string INF="1"; for(int i=0;i<1000;i++){ /*尽可能求一个大点的数用于路径长度的初始化*/ INF=multiple(INF,2); } while(cin>>n>>m){ string l="1"; memset(graph,0,sizeof(graph)); /*初始化*/ fill(dis,dis+n,INF); for(int i=0;i<m;i++){ cin>>a>>b; graph[a].push_back(Edge(b,l)); graph[b].push_back(Edge(a,l)); l=multiple(l,2); } Dijkstra(); for(int i=1;i<n;i++){ if(dis[i]==INF) cout<<-1<<endl; else cout<<Divide(dis[i])<<endl; } } return 0; } ------------------------------------------------------------------------ /*方法二,使用并查集,因为后面边的长度比前面所有边长之和还要长*/ /*所以后面加的边就不用再考虑,如果两个点不属于一个集合,*/ /*直接合并这两个点即可,此时长度一定是最短的*/ #include<iostream> #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<climits> #define INF INT_MAX #define N 101 using namespace std; struct Point{ int number; int distance; Point(int n, int d): number(n), distance(d) {} bool operator<(const Point &p) const{ return distance>p.distance; } }; struct Edge{ int to; int length; Edge(int t, int l): to(t), length(l) {} }; int dis[N]; vector<Edge> graph[N]; int father[N]; int height[N]; void Init(int n){ for(int i=0;i<n;i++){ father[i]=i; height[i]=0; } return ; } int Find(int x){ if(x!=father[x]){ father[x]=Find(father[x]); } return father[x]; } void Union(int x, int y){ x=Find(x); y=Find(y); if(x!=y){ if(height[x]<height[y]) father[x]=y; else if(height[x]>height[y]) father[y]=x; else{ father[y]=x; height[x]++; } } return ; } void Dijkstra(){ dis[0]=0; priority_queue<Point> Q; Q.push(Point(0,dis[0])); while(!Q.empty()){ int u=Q.top().number; Q.pop(); for(int i=0;i<graph[u].size();i++){ int v=graph[u][i].to; int d=graph[u][i].length; if(d+dis[u]<dis[v]){ dis[v]=d+dis[u]; Q.push(Point(v,dis[v])); } } } return ; } int main(){ int n,m; while(cin>>n>>m){ Init(n); memset(graph,0,sizeof(graph)); fill(dis,dis+n,INF); int len=1; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; if(Find(a)!=Find(b)){ /*两个点不属于一个集合*/ Union(a,b); graph[a].push_back(Edge(b,len)); graph[b].push_back(Edge(a,len)); } len=(len*2)%100000; } Dijkstra(); for(int i=1;i<n;i++){ if(dis[i]==INF) cout<<-1<<endl; else cout<<dis[i] % 100000<<endl; } } return 0; }
// 这道题有点变态,常规做法可以考虑构建大整数结构体,结合最短路径问题 // 由于题目中路径长度有特殊性质,后来的第k条道路比前面k-1条距离之和还要小 // 如果节点a和b在之前已经被联通,那么后来的可联通ab的道路肯定不是最短距离 // 所以,当a、b未联通,出现可以联通a与b的道路时: // 1. 首先联通a与b,更新dist[a][b] // 2. 同时更新a所在的连通域的节点与b所在连通域节点之间的组合: dist[x][y] = dist[x][a] + dist[a][b] + dist[b][y] // (由于x是a所在连通域内的节点,包括a自身,x与a必定已经联通,dist不为-1;y也同理 // 更新时的距离计算只要乘幂取模就行,可以忽略取模之后对幂运算大小的改变,此时大小已无关重要) // 3. 将a与b合并#include <iostream> using namespace std;int dist[105][105]={}; int parent[105] = {};int find(int x){ if (parent[x] == -1) return x; else{ int temp = find(parent[x]); parent[x] = temp; return temp; } }int get_mod(int base, int times){ int ans = 1; for (int i=0; i<times; i++){ ans *= base; ans %= 100000; } return ans; }int main(){ int n,m; cin >> n >> m; for (int i=0; i<n; i++) parent[i] = -1; for (int i=0; i<n; i++){ for (int j=0; j<n; j++) dist[i][j] = -1; dist[i][i] = 0; } for (int i=0; i<m; i++){ int a, b; cin >> a >> b; int pa = find(a); int pb = find(b); if (pa != pb){ int d = get_mod(2, i); // 核心部分:对a所在连通域和b所在连通域中所有的节点组合,都更新距离(此时必定是最小距离) for (int j=0; j<n; j++){ if (find(j) == pa){ for (int k=0; k<n; k++){ if (find(k) == pb){ dist[j][k] = dist[k][j] = (dist[j][a]+ d + dist[b][k])%100000; } } } } parent[pb] = pa; } } for (int i=1; i<n; i++) cout << dist[0][i] << endl; }
#include <iostream> #include <vector> using namespace std; const int N = 114; const int M = 514; const int mod = 100000; int n, m; struct Edge { int from; int to; int k; } edge[M]; int father[N]; vector<Edge> graph[N]; bool vis[N]; int dis[N]; int length[M]; int find(int x) { return x == father[x] ? x : father[x] = find(father[x]); } bool merge(int a, int b) { int fa = find(a); int fb = find(b); if(fa != fb) { father[fa] = fb; return true; } return false; } void dfs(int now, int len) { if(vis[now]) return; vis[now] = true; dis[now] = len; for(Edge& x: graph[now]) { dfs(x.to, (len + length[x.k]) % mod); } } int main() { length[0] = 1; for(int i = 1; i < M; i++) { length[i] = (length[i - 1] << 1) % mod; } while(cin >> n >> m) { for(int i = 0; i < n; i++) { father[i] = i; vis[i] = false; dis[i] = -1; graph[i].clear(); } for(int i = 0; i < m; i++) { cin >> edge[i].from >> edge[i].to; } int cnt = 0; for(int i = 0; cnt < n - 1 && i < m; i++) { if(merge(edge[i].from, edge[i].to)) { graph[edge[i].from].push_back({edge[i].from, edge[i].to, i}); graph[edge[i].to].push_back({edge[i].to, edge[i].from, i}); cnt++; } } dfs(0, 0); for(int i = 1; i < n; i++) cout << dis[i] << endl; } return 0; }
#include <climits> #include <iostream> #include <queue> #include <vector> using namespace std; const int MAXN = 101; const int INF = INT_MAX; //无穷设为很大的数 struct Edge { int to; //终点 int length; //长度 Edge(int to, int length): to(to), length(length) {} }; struct Point { int number; //点的编号 int distance; //源点到该点距离 Point(int number, int distance): number(number), distance(distance) {} bool operator<(const Point& p)const { return distance > p.distance; //距离小的优先级高 } }; vector<vector<Edge>>graph(MAXN); //邻接表实现的图 vector<int>dis(MAXN); //源点到各点距离 //并查集数据结构 vector<int>father(MAXN); //父亲结点 vector<int>height(MAXN); //结点高度 //并查集操作 void Initial(int n) { //初始化并查集 for (int i = 0; i < n; i++) { father[i] = i; //每个结点的父亲为自己 height[i] = 0; //每个结点的高度为0 } } int Find(int x) { //查找根结点 if (x != father[x]) { //路径压缩 father[x] = Find(father[x]); } return father[x]; } void Union(int x, int y) { //合并集合 x = Find(x); y = Find(y); if (x != y) { //矮树作为高树的子树 if (height[x] < height[y]) { father[x] = y; } else if (height[y] < height[x]) { father[y] = x; } else { father[y] = x; height[x]++; } } } //迪杰斯特拉算法求单源最短路径,s为源点 void Dijkstra(int s) { priority_queue<Point>myPriorityQueue; dis[s] = 0; myPriorityQueue.push(Point(s, dis[s])); while (!myPriorityQueue.empty()) { int u = myPriorityQueue.top().number; //离源点最近的点 myPriorityQueue.pop(); for (const auto& i : graph[u]) { int v = i.to; int d = i.length; if (dis[v] > dis[u] + d) { dis[v] = dis[u] + d; myPriorityQueue.push(Point(v, dis[v])); } } } } int main() { int n, m; while (cin >> n >> m) { fill(dis.begin(), dis.begin() + n, INF); //距离初始化为无穷 Initial(n); //初始化并查集 for (int k = 0, length = 1; k < m; k++, length *= 2, length %= 100000) { int from, to; //道路的起点和终点 cin >> from >> to; //由于第K条道路的长度为2^K,一定大于前K条道路长度之和 //因此,若第K条道路连接的两点已有路径,则第K条道路一定不会在最短路径中 //这种情况下,可将第K条道路忽略,否则再将其作为边加入图的邻接表中 if (Find(from) != Find(to)) { //判断两点是否连通(已有路径) Union(from, to); graph[from].push_back(Edge(to, length)); graph[to].push_back(Edge(from, length)); } } Dijkstra(0); for (int i = 1; i < n; i++) { cout << (dis[i] == INF ? -1 : dis[i] % 100000) << endl; } } return 0; }
#include <stdio.h> #include <stdlib.h> #define mod 100000 // 输入一条新路a<=>b后,会存在三层连接的发生: // 1.两个根结点a, b之间的连接 // 2.两个根节点与另一方的下属结点之间的连接 // 3.下属结点之间的连接 void init_dist(int N, int dist[N][N]){ for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ dist[i][j] = i==j ? 0 : -1; } } } void link_node(int N, int from, int to, int dist[N][N], int now_dis){ dist[from][to] = now_dis; dist[to][from] = now_dis; } void renew_dist(int N, int from, int to, int dist[N][N], int now_dis){ // 第一步 link_node(N, from, to, dist, now_dis); // 第二步 int waitlist[2][N], length0=0, length1=0; for(int i=0; i<N; i++){ if(from !=i && dist[from][i] != -1){ //i是from下属结点,让to和i连接,并让i入(from队) link_node(N, i, to, dist, (dist[from][i] + now_dis) % mod); waitlist[0][length0] = i; length0++; }else if(to!=i && dist[to][i] != -1){ //i是to的下属结点,让from和i连接,并让i入(to队) link_node(N, i, from, dist, (dist[to][i] + now_dis) % mod); waitlist[1][length1] = i; length1++; } } // 第三步 int a, b; //美观起见 for(int i=0; i<length0; i++){ a = waitlist[0][i]; for(int j=0; j<length1; j++){ b = waitlist[1][j]; link_node(N, a, b, dist, (dist[a][from] + dist[from][b]) % mod); } } } int main() { int N, M; int from, to; while (scanf("%d %d", &N, &M) != EOF) { int now_dis = 1; int dist[N][N]; init_dist(N, dist); for(int i=0; i<M; i++){ scanf("%d %d", &from, &to); if(dist[from][to] == -1){ renew_dist(N, from, to, dist, now_dis); } now_dis = (now_dis*2) % mod; } for(int i=1; i<N; i++){ printf("%d\n", dist[0][i]); } } return 0; }