#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int>pp;
const int MAX=200000;
int n,m,inp[MAX][4],outp[MAX];
bool vis[MAX];
unordered_set<int>f[MAX],b[MAX];
queue<int>q;
priority_queue<pp>pq;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
memset(vis,false,sizeof(vis));
cin>>n>>m;
for(int i=0;i<m;i++){
cin>>inp[i][0]>>inp[i][1]>>inp[i][2]>>inp[i][3];
inp[i][0]--;
inp[i][1]--;
f[inp[i][0]].insert(i);
b[inp[i][1]].insert(i);
}
for(int i=0;i<n;i++)if(f[i].size()==0)q.push(i);
while(!q.empty()){
int cur=q.front();
q.pop();
outp[cur]=-1;
for(auto&i:b[cur]){
if(vis[i])continue;
vis[i]=true;
f[inp[i][0]].erase(f[inp[i][0]].find(i));
if(f[inp[i][0]].size()==0)q.push(inp[i][0]);
}
}
for(int i=0;i<m;i++)if(!vis[i])pq.push({inp[i][2],i});
while(!pq.empty()){
pp cur=pq.top();
pq.pop();
if(vis[cur.second])continue;
vis[cur.second]=true;
int ai=inp[cur.second][0];
int bi=inp[cur.second][1];
f[ai].erase(f[ai].find(cur.second));
b[bi].erase(b[bi].find(cur.second));
if(f[ai].size()==0){
for(auto&i:b[ai])if(!vis[i])if(cur.first-inp[i][3]>inp[i][2])pq.push({cur.first-inp[i][3],i});
outp[ai]=cur.first;
}
}
for(int i=0;i<n-1;i++)cout<<outp[i]<<" ";
cout<<outp[n-1]<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
22348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
22348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
22348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
