Submission #1028753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1028753		underwaterkillerwhale	Robot (JOI21_ho_t4)	C++17	0 / 100	23 ms	10332 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define N 100005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
int n, m;
int a[N], c[N];
vector<ii>g[N];
namespace sub1
{
const int M1 = 1005, M2 = 2005;
ll d[M1], sum[M2][M2];
struct trip
{
    int w, node, color, idx;
};
struct cmp
{
    bool operator()(trip a, trip b)
    {
        return a.w > b.w;
    }
};
void bfs()
{
    for(int i = 1; i <= n; i++)
        d[i] = 1e18;
    priority_queue<trip, vector<trip>, cmp>q;
    q.push({0, 1, 0, 0});
    d[1] = 0;
    while(q.empty() != 1)
    {
        trip top = q.top();
        q.pop();
        int kc = top.w, u = top.node, color = top.color, idx1 = top.idx;
        for(ii i : g[u])
        {
            int v = i.F, idx2 = i.S;
            sum[u][color] += c[idx1];
            sum[u][a[idx1]] -= c[idx1];
            for(int j = 1; j <= m; j++)
            {
                if(a[idx2] == j)
                {
                    if(d[v] > kc + sum[u][j] - c[idx2])
                    {
                        d[v] = kc + sum[u][j] - c[idx2];
                        q.push({d[v], v, j, idx2});
                    }
                }
                else if(d[v] > kc + sum[u][j] + c[idx2])
                {
                    d[v] = kc + sum[u][j] + c[idx2];
                    q.push({d[v], v, j, idx2});
                }
            }
            sum[u][color] -= c[idx1];
            sum[u][a[idx1]] += c[idx1];
        }
    }
}
void deb()
{
    cout<<endl;
    for(int i=1;i<=n;i++)
        cout<<i<<": "<<d[i]<<"\n";
    cout<<endl;
}
void solve()
{
    for(int i = 1; i <= n; i++)
        for(ii j : g[i])
        {
            int idx = j.S;
            sum[i][a[idx]] += c[idx];
        }
    bfs();
//    deb();
    cout << (d[n] == 1e18 ? -1 : d[n]);
}
}
namespace sub2
{
void solve()
{
}
}
main()
{
//    freopen("BAI2.inp","r",stdin);
//    freopen("BAI2.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, z, w;
        cin >> x >> y >> z >> w;
        a[i] = z;
        c[i] = w;
        g[x].push_back({y, i});
        g[y].push_back({x, i});
    }
    if(n <= 1000 && m <= 2000)
        sub1::solve();
    else
        sub2::solve();
}
/**
4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

5 2
1 4 1 2
3 5 1 4

5 6
1 2 1 1
1 3 1 3
2 4 2 5
3 2 2 2
3 5 2 2
4 5 3 4
= 3
5 6
1 2 1 1
1 3 1 3
2 4 2 5
3 2 2 5
3 5 2 2
4 5 3 4
=3
5 6
1 2 1 1
1 3 1 3
2 4 2 5
3 2 3 5
3 5 2 2
4 5 3 4
=1
5 7
1 2 1 1
1 3 1 3
2 4 2 5
3 2 2 5
3 5 2 2
4 5 3 4
3 4 1 3

5 8
1 2 1 1
1 3 1 3
2 4 2 5
3 2 2 5
3 5 2 2
4 5 3 4
3 4 1 3
2 5 3 4
**/

Compilation message (stderr)

Main.cpp: In function 'void sub1::bfs()':
Main.cpp:53:36: warning: narrowing conversion of 'sub1::d[v]' from 'long long int' to 'int' [-Wnarrowing]
   53 |                         q.push({d[v], v, j, idx2});
      |                                 ~~~^
Main.cpp:59:32: warning: narrowing conversion of 'sub1::d[v]' from 'long long int' to 'int' [-Wnarrowing]
   59 |                     q.push({d[v], v, j, idx2});
      |                             ~~~^
Main.cpp: At global scope:
Main.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main()
      | ^~~~

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