[TIOJ] 1641. 貨物運送計劃

題目連結:http://tioj.infor.org/problems/1641

---

看完CBD的題解後，覺得自己滿蠢的，其實取個log後最dijkstra就好了www。我這裡是自己寫了個簡單(?的科學記號模板來用，做法就依樣是裸的dijkstra。

#include <bits/stdc++.h>
	using namespace std;
	#define PB push_back
	typedef pair<double,int> PDI;
	#define FF first
	#define SS second
	const int N = 10000 + 5;

	struct SciFi{
		double x; int p;
		SciFi(){x=0;p=0;}
		SciFi(double k){
			p = floor(log10(k));
			x = k / pow((double)10, p);
		}
		SciFi(double a, int b){
			x=a;p=b;
		}
		SciFi operator=(double k){
			p = floor(log10(k));
			x = k / pow((double)10, p);
			return *this;
		}
		SciFi operator*(SciFi k)const{
			int nP = p+k.p;
			double nX = x*k.x;
			int tp = floor(log10(nX));
			return SciFi(nX/pow((double)10, tp), nP+tp);
		}
		SciFi operator*=(SciFi k){
			p+=k.p;
			x*=k.x;
			int tp = floor(log10(x));
			p+=tp;
			x/=pow((double)10, tp);
			return *this;
		}
		SciFi operator+(SciFi k)const{
			int newP = std::min(k.p, p);
			double x1 = x*pow((double)10, p-newP);
			double x2 = k.x*pow((double)10, k.p-newP);
			x1+=x2;
			int tp = floor(log10(x1));
			newP+=tp;
			x1 /= pow((double)10, tp);
			return SciFi(x1, newP);
		}
		SciFi operator+=(SciFi k){
			int newP = std::min(k.p, p);
			double x1 = x*pow((double)10, p-newP);
			double x2 = k.x*pow((double)10, k.p-newP);
			x1+=x2;
			int tp = floor(log10(x1));
			newP+=tp;
			x1 /= pow((double)10, tp);
			x=x1;p=newP;
			return *this;
		}
		bool operator<(SciFi a)const{
			if(p == a.p) return x<a.x;
			return p<a.p;
		}
		bool operator>(SciFi a)const{
			if(p == a.p) return x>a.x;
			return p>a.p;
		}
		bool operator==(SciFi a)const{
			return p==a.p and x==a.x;
		}
	};
	typedef pair<SciFi,int> PSI;

	vector<PDI> G[N];
	bitset<N> visited;
	SciFi dis[N];

	int main(){
		int n, m, s, t; scanf("%d%d%d%d",&n,&m,&s,&t);
		for(int i=0;i<m;i++){
			int u, v;double x;
			scanf("%d%d%lf",&u,&v,&x);
			G[u].PB({x, v});
		}
		fill(dis, dis+n+1, SciFi(1, 10000));
		dis[s]=1;
		priority_queue<PSI,vector<PSI>,greater<PSI>> pq;
		pq.push({dis[s], s});
		while(!pq.empty()){
			SciFi d = pq.top().FF;
			int u = pq.top().SS;
			pq.pop();
			if(visited[u]) continue;
			for(auto i:G[u]){
				int v = i.SS;
				SciFi dd = i.FF+1;
				if(d*dd < dis[v]){
					dis[v] = d*dd;
					pq.push({dis[v], v});
				}
			}
		}
		printf("%.2lfe%c%03d\n", dis[t].x, "+-"[dis[t].p<0], abs(dis[t].p));
		return 0;
	}