C++14(g++5.4) 解法, 执行用时: 82ms, 内存消耗: 18908K, 提交时间: 2019-10-06 23:23:52

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;

const ll MAXN=5e5+7;
vector<pair<ll,ll>> g[MAXN];
ll d[MAXN];
priority_queue<P,vector<P>,greater<P> > que;
ll n,m,S,T;

void dis(){
	memset(d,0x3f,sizeof(d));
	d[S]=0;
	que.push(make_pair(0,S));
	while(que.size()){
		P now=que.top();
		que.pop();
		ll u=now.second;
		for(auto e:g[u]){
			ll v=e.first;
			ll c=e.second;
			if(d[u]+c<d[v]){
				d[v]=d[u]+c;
				que.push(make_pair(d[v],v));
			}
		}
	}
}

ll to(ll c){
	ll cnt=-1;
	while(c){
		cnt++;
		c/=2;
	}
	return cnt; 
}

const ll MOD=1e9+7;

ll solve(ll n){
	ll x=2;
	ll res=1;
	while(n){
		if(n&1){
			res=x*res%MOD;
		}
		x=x*x%MOD;
		n>>=1;
	}
	return res;
}

int main(){
	scanf("%lld%lld%lld%lld",&n,&m,&S,&T);
	ll u,v;ll c;
	for(ll i=1;i<=m;i++){
		scanf("%lld%lld%lld",&u,&v,&c);
		g[u].push_back(make_pair(v,to(c)));
	}
	dis();
	if(d[T]==0x3f3f3f3f3f3f3f3f){
		printf("-1\n");
	}
	else{
		ll res=solve(d[T]);
//		cout<<"***"<<d[T]<<endl;
		printf("%lld\n",res);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 78ms, 内存消耗: 6360K, 提交时间: 2018-11-29 17:34:45

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>mp;
vector<int>ve[50005];
vector<ll>va[50005];
ll d[50005],mod=1e9+7;
queue<int>q; 
bool mark[50005];
void spfa(int s){
	memset(d,0x3f3f,sizeof(d));
	d[s]=0;
	mark[s]=1;
	q.push(s);
	while(!q.empty()){
		int t=q.front();
		q.pop();
		mark[t]=0;
		for(int i=0;i<ve[t].size();i++){
			int x=ve[t][i];
			if(d[x]>d[t]+va[t][i]){
				d[x]=d[t]+va[t][i];
				if(mark[x])continue;
				q.push(x);
				mark[x]=1;
			} 
		}
		
	}
}
ll fun(ll x){
	//if(x==0)return 0;
	ll res=1,a=2;
	while(x){
		if(x&1)res=(res*a)%mod;
		a=(a*a)%mod;
		x>>=1;
	}
	return res;
}
int main(){
	for(ll i=2,j=1;i<=10000000000;i*=2,j++)
	mp[i]=j;
	int n,m,u,v,s,t;
	ll w;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld",&u,&v,&w);
		ve[u].push_back(v);
		va[u].push_back(mp[w]);
	}
	spfa(s);
	if(d[t]>=0x3f3f3f3f3f3f3f3f)
		printf("-1\n");
	else printf("%lld\n",fun(d[t]%(mod-1)));
    return 0;
}

Python3(3.5.2) 解法, 执行用时: 840ms, 内存消耗: 26880K, 提交时间: 2019-11-17 16:30:54

from math import log2
while 1:
    try:
        ini = input().split()
        (n, m, s, t) = [int(k) for k in ini]
        pa = {}
        for i in range(n+1):
            pa[i] = list()
        for i in range(m):
            tp = input().split()
            (si, di, wi) = [int(k) for k in tp]
            pa[si].append((di, log2(wi)))
        qu = [s]
        le = []
        for i in range(n+1):
            le.append(1024)
        le[s] = 0
        while len(qu) != 0:
            cur = qu[0]
            for pp in pa[cur]:
                (r, m) = pp
                l = le[cur]
                if (l+m) < le[r]:
                    le[r] = l+m
                    qu.append(r)
            qu.pop(0)
        if le[t] == 1024:
            print(-1)
        else:
            print(pow(2, int(le[t]), 1000000007))
    except:
        break