#define first x #define second y #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair <ll , ll> pii; const int N = 2e5 + 10,mod = 1e9 + 7; const int inf = 0x3f3f3f3f; ll h[N],e[N],w[N],ne[N],idx; ll n,m,s,t,c; ll num[N],dist[N],sum[N]; bool st[N]; ll minn = inf,maxn; void add(int a,int b,int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++; } void dijkstra(int mid) { memset(dist , -1 , sizeof dist); memset(st , 0 , sizeof st); dist[s] = 0; sum[s] = num[s]; priority_queue <pii , vector<pii> , greater<pii> > heap; heap.push({dist[s] , s}); while(heap.size()) { auto t = heap.top(); heap.pop(); int v = t.y; if(st[v]) { continue; } st[v] = 1; for(int i = h[v] ; i != -1 ; i = ne[i]) { int j = e[i]; dist[j] = max(dist[j] , w[i]); sum[j] = sum[v] + num[j]; if(dist[j] > mid || sum[j] > c) { continue; }else { heap.push({dist[j] , j}); } } } } void work() { cin>>n>>m>>s>>t>>c; memset(h , -1 , sizeof h); for(int i = 1 ; i <= n ; i++) { cin>>num[i]; } while(m--) { ll a,b,c; cin>>a>>b>>c; add(a , b , c); minn = min(minn , c); maxn = max(maxn , c); } ll l = minn,r = maxn; while(l < r) { ll mid = (l + r) >> 1; dijkstra(mid); if(dist[t] != -1) { r = mid; }else { l = mid + 1; } } cout<<r; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0); work(); }
以上代码样例结果是3,但是提交却ac了,之所以输出是3是因为49和50行应该在判断完可以接受以后再更改,代码如下
#define first x #define second y #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair <ll , ll> pii; const int N = 2e5 + 10,mod = 1e9 + 7; const int inf = 0x3f3f3f3f; int h[N],e[N],w[N],ne[N],idx; int n,m,s,t,c; int num[N],dist[N],sum[N]; bool st[N]; int minn = inf,maxn; void add(int a,int b,int c) { e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx++; } void dijkstra(int mid) { memset(dist , -1 , sizeof dist); memset(st , 0 , sizeof st); dist[s] = 0; sum[s] = num[s]; priority_queue <pii , vector<pii> , greater<pii> > heap; heap.push({dist[s] , s}); while(heap.size()) { auto t = heap.top(); heap.pop(); int v = t.y,dis = t.x; if(st[v]) { continue; } st[v] = 1; for(int i = h[v] ; i != -1 ; i = ne[i]) { int j = e[i]; if(max(dist[j] , w[i]) > mid || sum[v] + num[j] > c) { continue; }else { sum[j] = sum[v] + num[j]; dist[j] = max(dist[j] , w[i]); heap.push({dist[j] , j}); } } } } void work() { cin>>n>>m>>s>>t>>c; memset(h , -1 , sizeof h); for(int i = 1 ; i <= n ; i++) { cin>>num[i]; } while(m--) { int a,b,c; cin>>a>>b>>c; add(a , b , c); minn = min(minn , c); maxn = max(maxn , c); } int l = minn,r = maxn; while(l < r) { int mid = (l + r) >> 1; dijkstra(mid); if(dist[t] != -1) { r = mid; }else { l = mid + 1; } } cout<<r; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0),cout.tie(0); work(); }
以上代码是可以过样例的,但是却wa了,想知道为什么
全部评论
(0) 回帖