C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 588K, 提交时间: 2020-07-07 17:30:38

#include <bits/stdc++.h>
#define ll long long
#define INF 0x7fffffff 
using namespace std;
const int maxn = 505;
int n,m,x;
struct node{
	int l,r,ping,c; 
	bool operator <(const node &p) const{
		return double(ping)+double(x/c) > double(p.ping)+double(x/p.c);
	}
};
priority_queue <node> Q;
vector <node> V[maxn];
int main(){
    ios::sync_with_stdio(false);
    //freopen("1.in.txt","r",stdin);
	//freopen("1.out","w",stdout);	
	cin >> n >> m >> x;
	int l1,r1,ping1,c1;
	for(int i = 0;i < m;i++){
		cin >> l1 >> r1 >> ping1 >> c1;
		V[l1].push_back({l1,r1,ping1,c1});
		V[r1].push_back({r1,l1,ping1,c1});
	}
	for(int i = 0;i < V[1].size();i++)	Q.push(V[1][i]);
	while(Q.size()){
		node temp = Q.top();
		if(temp.r == n){
			ll ans = temp.ping+x/temp.c;
			cout << ans << endl;
			break;
		}
		Q.pop();
		for(int i = 0;i < V[temp.r].size();i++){
			if(temp.l == V[temp.r][i].r)	continue;
			Q.push({temp.r,V[temp.r][i].r,temp.ping+V[temp.r][i].ping,min(temp.c,V[temp.r][i].c)});
		}
	} 
	return 0;
}

C++ 解法, 执行用时: 17ms, 内存消耗: 464K, 提交时间: 2022-07-16 15:03:18

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
struct node{int w,v;};
int n,m,xx,ans=1e9;
int dis[510],h[510],vis[510];
vector<pair<int,node>>vt[510];
void dij(int minn){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	priority_queue<pii,vector<pii>,greater<pii>>q;
	q.push({0,1});
	dis[1]=0;
	while(q.size()){
		auto t=q.top().second;q.pop();
		if(vis[t]) continue;
		vis[t]=1;
		for(auto it:vt[t]){
			int nx=it.first,nw=it.second.w,nv=it.second.v;
			if(nv<minn) continue;
			dis[nx]=min(dis[nx],dis[t]+nw);
			if(!vis[nx]) q.push({dis[nx],nx});
		}
	}
}
int main(){
	cin>>n>>m>>xx;
	for(int i=1;i<=m;i++){
		int a,b,c,d;cin>>a>>b>>c>>d;
		h[i]=d;
		vt[a].push_back({b,node{c,d}});
		vt[b].push_back({a,node{c,d}});
	}
	for(int i=1;i<=m;i++){
		dij(h[i]);
		ans=min(ans,dis[n]+xx/h[i]);
	}
	cout<<ans;
} 

pypy3(pypy3.6.1) 解法, 执行用时: 185ms, 内存消耗: 25952K, 提交时间: 2020-06-26 22:43:14

#!/usr/bin/env python3
#
# Milk Routing
#
import sys, os, math
from collections import deque

def read_ints(): return list(map(int, input().split()))
#------------------------------------------------------------------------------#

n, m, x = read_ints()
g = [[] for _ in range(n)]
for _ in range(m):
	i, j, l, c = read_ints()
	i -= 1; j -= 1
	g[i].append((j, l, c))
	g[j].append((i, l, c))

q = deque()
q.append((0, 0, 1e18))
s = {}
for i in range(n): s[i] = []
s[0].append((0, 1e18))
while q:
	u, ll, cc = q.popleft()
	for v, l, c in g[u]:
		nl, nc = l + ll, min(cc, c)
		found = False
		for tl, tc in s[v]:
			if tl <= nl and tc >= nc:
				found = True
				break
		if not found:
			s[v].append((nl, nc))
			q.append((v, nl, nc))

ans = 1e18
for l, c in s[n - 1]:
	ans = min(ans, l + x // c)

print(ans)