Submission #1091815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091815		vu28082007	Robot (JOI21_ho_t4)	C++14	58 / 100	3016 ms	116796 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define taskname ""
#define ll long long
#define fi first
#define se second
#define pb push_back

const int N = 2e5+7;
ll n, m, dist[N],a,b,c,p;
vector<array<ll, 3>> adj[N];
map<ll,vector<array<ll,2>>> adj2[N];
map<ll,ll> dist2[N];
map<ll,ll> sum[N];
void mvu()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c >> p;
        adj[a].pb({b,c,p});
        adj[b].pb({a,c,p});
        adj2[a][c].pb({b,p});
        adj2[b][c].pb({a,p});
        sum[a][c]+=p;
        sum[b][c]+=p;
    }
    for (int i = 2; i <= n; i++) dist[i]=1e18;
    for (int i = 1; i <= n; i++)
    {
        for (auto j : adj[i])
        {
            dist2[i][j[1]]=1e18;
        }
    }
    priority_queue<array<ll,3>, vector<array<ll,3>>, greater<>> pq;
    pq.push({0,1,0});
    while(!pq.empty())
    {
        auto k = pq.top();
        pq.pop();
        if(k[2]==0)
        {
            for (auto j : adj[k[1]])
            {
                if(k[0] > dist[j[0]]) continue;
                if(dist[j[0]] > k[0]+sum[k[1]][j[1]]-j[2])
                {
                    dist[j[0]]=k[0]+sum[k[1]][j[1]]-j[2];
                    pq.push({dist[j[0]], j[0], 0});
                }
                if(dist[j[0]] > k[0] + j[2])
                {
                    dist[j[0]]=k[0]+j[2];
                    pq.push({dist[j[0]], j[0]});
                }
                if(dist2[j[0]][j[1]] > k[0])
                {
                    dist2[j[0]][j[1]]=k[0];
                    pq.push({k[0], j[0], j[1]});
                }
            }
        }
        else
        {
            if(k[0] > dist2[k[1]][k[2]]) continue;
            for (auto j : adj2[k[1]][k[2]])
            {
                if(dist[j[0]] > k[0] + sum[k[1]][k[2]] - j[1])
                {
                    dist[j[0]] = k[0] + sum[k[1]][k[2]] - j[1];
                    pq.push({dist[j[0]], j[0], 0});
                }
            }
        }
    }
    if(dist[n]==1e18) cout << -1;
    else cout << dist[n];
}

int main()
{
    if(fopen(taskname".inp", "r"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(false);
    mvu();
    return 0;
}

Compilation message (stderr)

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

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