临海网站制作,wordpress哪个好用,网站建设老李教学网站,wordpress 默认插件题干#xff1a;
考虑一个包含 N 个顶点的无向图#xff0c;编号从 1 到 N#xff0c;并包含 M 条边。编号为 1 的顶点对应了一个矿藏#xff0c;可从中提取珍稀的矿石。编号为 N 的顶点对应了一个矿石加工厂。每条边有相应的通行时间 (以时间单位计)#xff0c;以及相应…题干
考虑一个包含 N 个顶点的无向图编号从 1 到 N并包含 M 条边。编号为 1 的顶点对应了一个矿藏可从中提取珍稀的矿石。编号为 N 的顶点对应了一个矿石加工厂。每条边有相应的通行时间 (以时间单位计)以及相应的运载量 (以矿石单位计)。现决定使用一条路径将从矿藏中提取的矿石运送到加工厂。这条路径应当具有尽可能高的运载量以便并行运输尽可能多的矿石。路径的运载量等于它的各边的最小运载量。然而这些矿石很敏感一旦从矿藏中提取出来就会在 T 个时间单位之后开始分解除非在这个时间截止之前到达工厂。因此所选路径的总通行时间 (各条边的通行时间之和) 应当小于或等于 T。
输入
输入的第 1 行包含一个整数 X表示测试数据的组数。
对于每组测试数据第 1 行包含了以空格分隔的三个整数N (2 ≤ N ≤ 10000)M (1 ≤ M ≤ 50000) 和 T (1 ≤ T ≤ 500000)。接下来的 M 行每行包含以空格分隔的四个整数A, B, C, D表示顶点 A 和 B 之间有一条边边的运载量是 C (1 ≤ C ≤ 2×10^9)边的通行时间是 D (1 ≤ D ≤ 50000)。A 和 B 是介于 1 到 N 之间的不同整数。任意两个顶点之间至多有一条边。
输出
对于每组测试数据在一行里输出从矿藏到工厂的路径的最大运载量考虑到通行时间的约束。在满足通行时间约束的条件下矿藏和工厂之间总是存在至少一条路径。
示例输入
2 2 1 10 1 2 13 10 4 4 20 1 2 1000 15 2 4 999 6 1 3 100 15 3 4 99 4
示例输出
13 99
解题报告 题目不难给定一个T求起点到终点的在时间T内的 能够装载的最大矿石。二分这个装载数最短路check就行了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
const int INF 0x3f3f3f3f;
struct Edge {int to,ne,w,zzl;//装载量
} e[MAX];
int tot,n,m,T;
int head[MAX],dis[MAX],vis[MAX];
struct Point {int pos;int c;Point(){}Point(int pos,int c):pos(pos),c(c){}bool operator(const Point b)const{return c b.c;}
};
void add(int u,int v,int w,int zzl) {e[tot].to v;e[tot].w w;e[tot].zzlzzl;e[tot].ne head[u];head[u] tot;
}
int Dijkstra(int x) {for(int i 1; in; i) dis[i] INF,vis[i] 0;dis[1]0;priority_queuePoint pq;pq.push(Point(1,0));while(!pq.empty()) {Point cur pq.top();pq.pop();if(vis[cur.pos]) continue;vis[cur.pos] 1;for(int i head[cur.pos]; ~i; i e[i].ne) {int v e[i].to;if(vis[v]) continue;if(e[i].zzl x) continue;if(dis[v] dis[cur.pos] e[i].w) {dis[v] dis[cur.pos] e[i].w;pq.push(Point(v,dis[v]));}}}return dis[n];
}
int main()
{int t;cint;while(t--) {scanf(%d%d%d,n,m,T);tot0;int l INF,r 0,mid,ans;for(int i 1; in; i) head[i] -1;for(int a,b,c,d,i 1; im; i) {scanf(%d%d%d%d,a,b,c,d);add(a,b,d,c);add(b,a,d,c);r max(r,c);l min(l,c);}while(lr) {mid (lr)1;if(Dijkstra(mid) T) ans mid,l mid1;else r mid-1; }printf(%d\n,ans);}return 0 ;
}