| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 60913 | Accepted: 18405 |
Description
Input
Output
Sample Input
1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0
Sample Output
5250
存在等级关系，而且酋长不是等级最高的，这个只需要遍历就可以解决
建从1到其他点的有向图，且当直接距离超过了m，便不能建图
当求出最短路时候，遍历每一个d[i]+=a[i].val(商品价值）
OK
#include <iostream> #include <cmath> #include <cstdio> #include <cstring> #include <string> #include <map> #include <iomanip> #include <algorithm> #include <queue> #include <stack> #include <set> #include <vector> //const int maxn = 1e5+5; #define ll long long ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} ll lcm(ll a,ll b){return a/gcd(a,b)*b;} #define MAX INT_MAX #define FOR(i,a,b) for( int i = a;i <= b;++i) #define bug cout<<"--------------"<<endl using namespace std; int n,m,tot; int ver[11000],edge[11000],next[11000],head[11000],vis[11000],d[11000]; vector<pair<int,int> >vec[500]; struct node { int val,w,nub; }a[500]; void add(int x,int y,int z) { ver[++tot] = y,edge[tot] = z,next[tot] = head[x],head[x] = tot; } int dijiestra(int l,int r) { priority_queue<pair<int,int> >que; memset(vis,0,sizeof(vis)); memset(d,0x3f,sizeof(d)); d[1] = 0; que.push(make_pair(0,1)); while(que.size()) { int x = que.top().second;que.pop(); if(vis[x] == 1) continue; vis[x] = 1; for(int i= head[x];i;i=next[i]) { int y = ver[i],z = edge[i]; if( d[y] > d[x] + z && a[y].w>=l && a[y].w<=r) { d[y] = d[x] + z; que.push(make_pair(-d[y],y)); } } } int minn = 9999999; for(int i = 1;i<=n;++i) { if(a[i].w>=l && a[i].w<=r) { minn=min(minn,d[i]+a[i].val); } } return minn; } int main() { ios::sync_with_stdio(false); cin>>m>>n; for(int i=1;i<=n;++i) { cin>>a[i].val>>a[i].w>>a[i].nub; for(int j=1;j<=a[i].nub;++j) { int x,y; cin>>x>>y; vec[i].push_back(make_pair(x,y)); } } for(int i=1;i<=n;++i) { for(int j=0;j<vec[i].size();++j) { int y = vec[i][j].first; int z = vec[i][j].second; if(abs(a[i].w-a[i].w) > m) continue; add(i,y,z); } } int temp = a[1].w; int minn = 99999999; for(int i=temp-m;i<=temp;++i) { minn=min(minn,dijiestra(i,i+m)); } cout<<minn<<endl; }
原文：https://www.cnblogs.com/jrfr/p/11371090.html