思路供应者@dfsyyds

#include <bits/stdc++.h>
#define lll long long
#define rint register int
using namespace std;
struct ff { //empire
	vector <int> qx;
	vector <int> qw;
	vector <int> qt;
} ct[1001];
bool b[1001]= {0};
int n,m;
double ans=0.0,aaa,bbb;
void cheak(int a,int b) {
	double aa=double(a),bb=double(b);
	if(ans<=bb/aa){
		ans=bb/aa;
		aaa=aa,bbb=bb;
	} 
}
void dfs(int x,int sum,int mn) {
	if(aaa>0) if(mn*1000000/sum<=bbb*1000000/aaa) return;
	if(x==n) {
		cheak(sum,mn);
		return;
	}
	for(rint i=0; i<=ct[x].qx.size()-1; i++) {
		int xx=ct[x].qx[i];
		//cout<<xx<<endl;
		if(b[xx]==0) {
			b[xx]=1;
			dfs(xx,sum+ct[x].qw[i],min(mn,ct[x].qt[i]));
			b[xx]=0;
		}
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for(rint i=1; i<=m; i++) {
		rint u,v,w,t;
		scanf("%d%d%d%d",&u,&v,&w,&t);
		ct[u].qx.push_back(v);
		ct[u].qw.push_back(w);
		ct[u].qt.push_back(t);
		ct[v].qx.push_back(u);
		ct[v].qw.push_back(w);
		ct[v].qt.push_back(t);
	}
	b[1]=1;
	dfs(1,0,0x3f3f3f3f);
	ans*=1000000.0;
	int pp=int(ans);
	printf("%d",pp);
	return 0;
}

朴素的dfs，只是加了dfs函数的第一行的剪枝。

我都不敢相信这种剪枝不开O2能A！！！！！ 而且剩余时间非常充裕