#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll inf=1e9;
ll n,m,i,j,k,l,r,x,y,z,w,s,t,dp[110000],h[110000],d[110000];
pair<ll,ll> p[110000];
queue<ll> q;
vector<pair<ll,ll>> v[110000];
int main()
{
scanf("%d %d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d %d",&x,&y,&z,&w);
p[i]={x,y};
d[i]={w-z};
}
for(i=0;i<=n;i++)
{
for(j=1;j<=m;j++)
{
v[i*(n+1)+p[j].first].push_back({(i+1)*(n+1)+p[j].second,d[j]});
h[(i+1)*(n+1)+p[j].second]++;
}
}
for(i=1;i<=100000;i++)
{
dp[i]=-inf;
}
dp[1]=0;
for(i=1;i<=100000;i++)
{
if(h[i]==0)
q.push(i);
}
while(!q.empty())
{
x=q.front();
q.pop();
for(i=0;i<v[x].size();i++)
{
// printf("[%lld]",v[x][i].first);
y=v[x][i].first;
z=v[x][i].second;
dp[y]=max(dp[y],dp[x]+z);
h[y]--;
if(h[y]==0)
q.push(y);
}
}
for(i=1;i<=n;i++)
{//printf("(%lld)\n",dp[(n+1)*i+1]);
if(dp[(n+1)*i+1]>0)
{
printf("%d %d",i,dp[(n+1)*i+1]);
return 0;
}
}
}
Compilation message
utrka.cpp: In function 'int main()':
utrka.cpp:40:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(i=0;i<v[x].size();i++)
| ~^~~~~~~~~~~~
utrka.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
11 | scanf("%d %d",&n,&m);
| ~~~~~^~~~~~~~~~~~~~~
utrka.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
14 | scanf("%d %d %d %d",&x,&y,&z,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
3672 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
