题目大意:
在 n 个点 m 条边的无向图中 需要运送 X 单位牛奶
每条边有隐患 L 和容量 C 则这条边上花费时间为 L+X/C
求从点 1 到点 n 的最小花费
优先队列维护 L+X/C 最小 广搜到点 n
- #include <bits/stdc++.h>
- using namespace std;
- #define LL long long
- #define INF 0x3f3f3f3f
- #define mem(i,j) memset(i,j,sizeof(i))
- #define inc(i,l,r) for(int i=l;i<=r;i++)
- #define dec(i,r,l) for(int i=r;i>=l;i--)
- const int N=2000+5;
- const int mod=1e9+7;
- int n,M;
- LL X;
- struct NODE {
- int u,v; LL L,C;
- bool operator <(const NODE& p) const {
- return (double)L+(double)X/C> (double)p.L+(double)X/p.C;
- }
- };
- vector<NODE>G[505];
- int main()
- {
- while(~scanf("%d%d%lld",&n,&M,&X)) {
- inc(i,1,n) G[i].clear();
- inc(i,1,M) {
- int u,v; LL l,c;
- scanf("%d%d%lld%lld",&u,&v,&l,&c);
- G[u].push_back({u,v,l,c});
- G[v].push_back({v,u,l,c});
- }
- LL ans;
- priority_queue <NODE> q;
- while(!q.empty()) q.pop();
- q.push({1,1,0,INF});
- while(!q.empty()) {
- NODE e=q.top(); q.pop();
- if(e.v==n) {
- ans=e.L+X/e.C; break;
- }
- int len=G[e.v].size()-1;
- inc(i,0,len) {
- NODE t=G[e.v][i];
- if(t.v==e.u) continue;
- q.push({e.v,t.v,e.L+t.L,min(e.C,t.C)});
- }
- }
- printf("%lld\n",ans);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2990351.html