C++(clang++11) 解法, 执行用时: 30ms, 内存消耗: 892K, 提交时间: 2021-05-08 15:46:26

#include<bits/stdc++.h>
using namespace std;

struct edge
{
	int to,p,d,next;
	edge(){}
	edge(int a,int b,int c,int d):to(a),p(b),d(c),next(d){}
}E[20005];
struct node
{
	long long x,h;
	bool operator<(const node &a)const
	{
		return a.h<h;
	}
}f;
priority_queue<node>Q;
int n,m,tot=0,head[10005];
long long dis[2][10005];
void add(int x,int y,int p,int d)
{
	E[++tot]=edge(y,p,d,head[x]);
	head[x]=tot;
}
void dij(int sx,int w,bool id)
{
	int i,j,p;
	long long d;
	for(i=1;i<=n;i++)dis[id][i]=1e18;
	dis[id][sx]=0,Q.push({sx,0});
	while(!Q.empty())
	{
		f=Q.top(),Q.pop();
		if(dis[id][f.x]<f.h)continue;
		for(i=head[f.x];i;i=E[i].next)
		{
			j=E[i].to,p=E[i].p,d=E[i].d;
			if(p<w)continue;
			if(dis[id][j]>f.h+d)dis[id][j]=f.h+d,Q.push({j,dis[id][j]});
		}
	}
}
int main()
{
	int i,j,sx,ex,w,d,u,v,p,dd,l,r,mid,ans=-1;
	scanf("%d%d%d%d%d%d",&n,&m,&sx,&ex,&w,&d);
	while(m--)scanf("%d%d%d%d",&u,&v,&p,&dd),add(u,v,p,dd),add(v,u,p,dd);
	dij(ex,w,1);
	for(l=1,r=1e9;l<=r;)
	{
		mid=(l+r)>>1;
		dij(sx,mid+w,0);
		if(dis[0][ex]+dis[1][sx]>d)r=mid-1;
		else ans=mid,l=mid+1;
	}
	printf("%d\n",ans);
    return 0;
}

Python3(3.9) 解法, 执行用时: 1817ms, 内存消耗: 8664K, 提交时间: 2021-05-11 12:28:46

n, m, x, y, w, d = map(int, input().strip().split())
graph = [list() for _ in range(n + 1)]
for i in range(m):
    u, v, p, dis = map(int, input().strip().split())
    graph[u].append([v, p, dis])
    graph[v].append([u, p, dis])


from queue import PriorityQueue


def check(line):
    global n, m, x, y
    dis = [10000000000] * (n + 1)
    flag = [0] * (n + 1)
    dis[x] = 0
    q = PriorityQueue()
    q.put((0, x))
    while not q.empty():
        tmp, node = q.get()
        if flag[node] == 1:
            continue
        flag[node] = 1
        for a, b, c in graph[node]:
            if dis[a] > dis[node] + c and b >= line:
                dis[a] = dis[node] + c
                q.put((dis[a], a))
    return dis[y]


lx = check(w)


left = w
right = 1000000000
ans = -1
while left <= right:
    mid = (left + right) // 2
    if check(mid) + lx <= d:
        ans = mid
        left = mid + 1
    else:
        right = mid - 1
if ans == w or ans == -1:
    print(-1)
else:
    print(ans - w)