[USACO 2015 Jan S]Meeting Time

The first input line contains N and M, separated by a space.
Each of the following M lines describes a path using four integers A B
C D, where A and B (with A < B) are the fields connected by the path,
C is the time required for Bessie to follow the path, and D is the
time required for Elsie to follow the path. Both C and D are in the
range 1..100.

A single integer, giving the minimum time required for Bessie and
Elsie to travel to their favorite field and arrive at the same moment.
If this is impossible, or if there is no way for Bessie or Elsie to reach
the favorite field at all, output the word IMPOSSIBLE on a single line.

pypy3(pypy3.6.1) 解法, 执行用时: 569ms, 内存消耗: 50824K, 提交时间: 2020-09-19 14:19:16

#!/usr/bin/env python3
#
# Meeting Time
#
import sys, os
from collections import deque

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

n, m = read_ints()
g = [[] for _ in range(n)]
for _ in range(m):
	a, b, c, d = read_ints()
	if a > b: a, b = b, a
	a -= 1; b -= 1
	g[a].append((b, c, d))

a = set()
b = set()

vi = [0] * 1000001
q = deque([(0, 0)])
while q:
	u, w = q.pop()
	for v, c, d in g[u]:
		x = (w + c) * 100 + v
		if vi[x] == 0:
			vi[x] = 1
			q.append((v, w + c))
			if v == n - 1: a.add(w + c)
vi = [0] * 1000001
q = deque([(0, 0)])
while q:
	u, w = q.pop()
	for v, c, d in g[u]:
		x = (w + d) * 100 + v
		if vi[x] == 0:
			vi[x] = 1
			q.append((v, w + d))
			if v == n - 1: b.add(w + d)

ans = 'IMPOSSIBLE'
for x in sorted(a):
	if x in b:
		ans = x
		break
print(ans)

C++14(g++5.4) 解法, 执行用时: 90ms, 内存消耗: 3388K, 提交时间: 2020-09-23 16:17:41

#include<cstdio>
using namespace std;
int n,m,i,j,k,s1,s2,x,y,ans,a[101][101],b[101][101],f[101][10100],h[101][10100];
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&x,&y,&s1,&s2);
		a[x][y]=s1;
		b[x][y]=s2;
	}
	f[1][0]=1;
	for(i=2;i<=n;i++)
	for(j=1;j<i;j++)
	if (a[j][i]>0)
	for(k=n*100-a[j][i];k>=0;k--)
	if (f[j][k]>0)
		f[i][k+a[j][i]]=1;
	h[1][0]=1;
	for(i=2;i<=n;i++)
	for(j=1;j<i;j++)
	if (b[j][i]>0)
	for(k=n*100-b[j][i];k>=0;k--)
	if (h[j][k]>0)
		h[i][k+b[j][i]]=1;
	ans=2147483647;
	for(j=1;j<=n*100;j++)
		if (f[n][j]&&h[n][j])
			if (j<ans)
				ans=j;
	if (ans!=2147483647)
		printf("%d\n",ans);
	else
		printf("IMPOSSIBLE\n");
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 504K, 提交时间: 2020-09-21 15:42:02

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=105,M=N*N;
struct Edge{int to,w,w2,nxt;}e[M];
int n,m,fst[N],tote;bool f[M][N],g[M][N];
void adde(int u,int v,int w,int w2){e[++tote]=(Edge){v,w,w2,fst[u]};fst[u]=tote;}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v,w,w2;i<=m;i++)scanf("%d%d%d%d",&u,&v,&w,&w2),adde(u,v,w,w2);
	f[0][1]=g[0][1]=true;
	for(int t=0;t<M;t++){
		if(f[t][n]&&g[t][n]){printf("%d\n",t);return 0;}
		for(int i=1;i<=n;i++){
			if(f[t][i]){for(int j=fst[i];j;j=e[j].nxt)f[t+e[j].w][e[j].to]=true;}
			if(g[t][i]){for(int j=fst[i];j;j=e[j].nxt)g[t+e[j].w2][e[j].to]=true;}
		}
	}
	puts("IMPOSSIBLE");
	return 0;
}

详情