题解 | #最短路径#

Dijkstra算法的暴力修正，用“相对距离”来替代“绝对距离”

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
#include <stack>

using namespace std;

//本题的特别之处，序号大小关系就代表了长度大小关系 

//这个长度设计有个特点：所有前面边的长度加起来都比下一个长度小 不过我的做法没用到这一点

const int MAXN = 100 + 10;
const int MAXM = 500 + 10;
const int INF = INT_MAX; 

int Quickpower(int xx, int n){
	long long ans = 1;
	long long x = xx;
	while(n){
		if(n%2){
			ans *= x;
			ans %= 100000;
		}
		x *= x;
		x %= 100000;
		n /= 2;
	}
	return ans;
}

class Edge{
public:
	int to;
	int length;
	int number;//边的序号，相对长度 
	Edge(int t, int l, int n):to(t),length(l),number(n){}
};


vector<Edge> graph[MAXN];

int dis[MAXN];//存模1e5后的真实距离

vector<int> redis[MAXN];//相对距离序列 

bool rediscmp(vector<int> &a, vector<int> &b){//a定为需要“合并结算”的那个吧  返回是否小于吧 
	sort(a.begin(), a.end());
	sort(b.begin(), b.end(), greater<int>());
	stack<int> sta;
	for(int i=0; i<a.size(); i++){
		if(i == 0){
			sta.push(a[i]);
			continue;
		}
		int tmp1 = sta.top();
		int tmp2 = a[i];
		if(tmp1 == tmp2){
			sta.pop();
			sta.push(tmp1 + 1);
		}else{
			sta.push(tmp2);
		}
	}
	a.clear();
	while(!sta.empty()){
		a.push_back(sta.top());
		sta.pop();
	}
	//此时合并操作完成，可以开始比较了
	int i=0;
	while(1){//直到比较出结果为止 
		if(i == a.size() && i == b.size()){//两个序列相等 那随便吧。返回个大于吧， 避免更新 
			return false;
		}else if(i == a.size() && i < b.size()){//前面一直相等，b那边有剩 ，a比b小 
			return true;
		}else if(i < a.size() && i == b.size()){//a比b大 
			return false;
		}else if(a[i] == b[i]){//从这行开始，都是没到尽头的情况  当前相等，比下一个 
			i++;
			continue;
		}else if(a[i] < b[i]){
			return true;
		}else{
			return false;
		}
	}
}

class Point{
public:
	int number;
	int distance;//优化为"相对距离"
	Point(int n, int d):number(n), distance(d){}
	bool operator<(const Point &p) const {
		return rediscmp(redis[p.number], redis[number]);
	}
};

void Dijkstra(int x){//x是起点的序号 
	priority_queue<Point> q;
	dis[x] = 0;
	redis[x].clear();
	redis[x].push_back(-1);
	q.push(Point(x, dis[x]));
	while(!q.empty()){
		int u = q.top().number;
		q.pop();
		for(int i=0; i<graph[u].size(); i++){
			int t = graph[u][i].to;
			int l = graph[u][i].length;
			int r = graph[u][i].number;
			//思考一下到底如何合理使用这个“序号”
			//比如 两个 2的29次方 打平 一个 2的30次方 
			//有个思路：“相对距离”用一个指数序列来描述，而非一个数  序列从大到小排序
			//u是a， t是b
			//不能真的去把redis[u]给改变了
			vector<int> a;
			a.assign(redis[u].begin(), redis[u].end());
			a.push_back(r);
			if(rediscmp(a, redis[t])){//则经过a的这条路更优，把t的路径改掉 
				redis[t].clear();
				redis[t].assign(a.begin(), a.end());
				dis[t] = (dis[u] + l)%100000;
				q.push(Point(t, dis[t]));
			}
		}
	}
	return;
}

int main(){
	int n, m;
	while(scanf("%d%d", &n, &m) != EOF){
		int from, to, length;
		memset(graph, 0, sizeof(graph));
		fill(dis, dis+n+1, INF);
		for(int i=0; i<MAXN; i++){
			redis[i].push_back(INF);
		}
		for(int i=0; i<m; i++){//往graph里面写入边信息 
			scanf("%d%d", &from, &to);
			length = Quickpower(2, i);
			graph[from].push_back(Edge(to, length, i));
			graph[to].push_back(Edge(from, length, i));
		}
		Dijkstra(0);
		for(int i=1; i<n; i++){
			if(dis[i] == INF){
				printf("-1\n");
			}else{
				printf("%d\n", dis[i]);
			}
		}
	}
	return 0;
}