제출 #959508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959508		edogawa_something	Railway Trip (JOI17_railway_trip)	C++17	0 / 100	1 ms	604 KiB

railway_trip

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
#define F first
#define S second
#define pb push_back
#define all(v) v.begin(),v.end()
const ll M=310;
const ll inf=2e18;
ll n,m,a[M],b[M],c[M];
bool rev[M];
vii v[M];
set<ll>rv[M];
ll calc(){
  for(int i=0;i<n+1;i++)
  c[i]=0;
  for(int i=0;i<m;i++){
    if(rev[i]){
      c[1]++;
      c[a[i]]--;
      c[b[i]]++,c[n+1]--;
    }
    else{
      c[a[i]]++;
      c[b[i]]--;
    }
  }
  ll cur=0,res=0;
  for(int i=1;i<=n;i++){
    cur+=c[i];
    res=max(res,cur);
  }
  return res;
}
int main(){
  ios_base::sync_with_stdio(0),cin.tie(0);
  cin>>n>>m;
  for(int i=0;i<m;i++){
    cin>>a[i]>>b[i]>>c[i];
    if(a[i]>b[i])
    swap(a[i],b[i]);
  }
  for(int i=1;i<=n;i++)
  c[i]=0;
  ll ans=inf;
  for(int i=0;i<(1<<m);i++){
    for(int bit=0;bit<m;bit++){
      rev[bit]=((i&(1<<bit))>0);
    }
    ans=min(ans,calc());
  }
  cout<<ans<<'\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 25
• Subtask 4: 0 / 55