제출 #480340

#제출 시각아이디문제언어결과실행 시간메모리
480340nicolaalexandraRestore Array (RMI19_restore)C++14
0 / 100
10 ms716 KiB
#include <bits/stdc++.h> #define DIM 10010 #define INF 2000000000 using namespace std; vector <pair<int,int> > L[DIM]; deque <int> c; int viz[DIM],sp[DIM]; int n,m,i,j,x,y,k,val; void add_edge (int x, int y, int cost){ L[x].push_back(make_pair(y,cost)); //cout<<x<<" "<<y<<" "<<cost<<"\n"; } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>m; for (i=1;i<=m;i++){ cin>>x>>y>>k>>val; x++, y++; if (val) add_edge(y,x-1,-(y-x-k)); else add_edge(x-1,y,k); } for (i=1;i<=n;i++){ add_edge(i-1,i,1); sp[i] = INF; } c.push_back(0); viz[0] = 1; sp[0] = 0; while (!c.empty()){ int nod = c.front(); c.pop_front(); viz[nod] = 0; for (auto it : L[nod]){ int vecin = it.first, cost = it.second; if (sp[nod] + cost < sp[vecin]){ sp[vecin] = sp[nod] + cost; if (!viz[vecin]){ viz[vecin] = 1; c.push_back(vecin); }}}} for (i=1;i<=n;i++) cout<<1-(sp[i]-sp[i-1])<<" "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...