Submission #1292367

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292367		lisoth	Robot (JOI21_ho_t4)	C++20	0 / 100	3120 ms	1055404 KiB

Main

#include<bits/stdc++.h>
using ll=long long;
const int N=1e6+5;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define F(i,a,b,c) for(int i=a;i<=b;i+=c)
#define fo(i,a,b,c) for(int i=a;i>=b;i-=c)
#define pb push_back
const int MOD=1e9+7;
#define el cout<<'\n'
#define all(x) x.begin(),x.end()
#define name "robot1"
using namespace std;
int n,m;
struct tri
{
    int a,b,c,p;
} edge[N];
int par[N];
int findr(int u)
{
    return par[u]<0 ? u : par[u]=findr(par[u]);
}
void dsu(int u,int v)
{
    u=findr(u),v=findr(v);
    if(u==v) return;
    if(par[u]>par[v]) swap(u,v);
    par[u]+=par[v];
    par[v]=u;
}
vector<pii> g[N];
map<pii,int> mp;
struct ba
{
    int fi,se,th;
};
vector<ba> f[N];
void init()
{
    memset(par,-1,sizeof(par));
    cin>>n>>m;
    F(i,1,m,1)
    {
        int a,b,c,p;cin>>a>>b>>c>>p;
        edge[i]={a,b,c,p};
        dsu(a,b);
        mp[{a,c}]+=p;
        mp[{b,c}]+=p;
        f[a].pb({b,c,p});
        f[b].pb({a,c,p});
    }
}
ll dp[N];
void solve()
{
    priority_queue<pll,vector<pll>,greater<pll>> h;
    F(u,1,n,1)
    {
        for(auto [v,c,p]:f[u])
        {
            int cost=min(p,mp[{u,c}]-p);
            g[u].pb({v,cost});
        }
    }
    F(i,2,n,1) dp[i]=LLONG_MAX;
    h.push({0,1});
    while(h.size())
    {
        auto [d,u]=h.top();h.pop();
        if(d>dp[u]) continue;
        for(auto [v,w]:g[u])
            if(dp[v]>d+w)
                h.push({dp[v]=d+w,v});
    }
    cout<<dp[n];
}
void process()
{
    if(findr(1)!=findr(n))
    {
        cout<<-1;
        return;
    }
    solve();
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    //input:
    init();
    clock_t begin = clock();
    //code:
    process();
    clock_t end = clock();
    cerr<<endl<<"Time run: "<<(float)(end-begin)/CLOCKS_PER_SEC<<" s"<<endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:96:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 34
• Subtask 2: 0 / 24
• Subtask 3: 0 / 42