Submission #554373

#	Time	Username	Problem	Language	Result	Execution time	Memory
554373		andrei_boaca	Robot (JOI21_ho_t4)	C++17	0 / 100	137 ms	15128 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll n,m,dist[100005];
struct date
{
    ll nod,cul,cost;
};
vector<date> muchii[100005];
bool bycul(date a, date b)
{
    if(a.cul!=b.cul)
        return a.cul<b.cul;
    return a.cost<b.cost;
}
void bfs()
{
    for(int i=1;i<=n;i++)
        dist[i]=-1;
    dist[1]=0;
    queue<ll> coada;
    coada.push(1);
    while(!coada.empty())
    {
        ll nod=coada.front();
        coada.pop();
        for(auto j:muchii[nod])
        {
            ll node=j.nod;
            ll cost=j.cost;
            if(dist[node]==-1||dist[node]>cost+dist[nod])
            {
                dist[node]=dist[nod]+cost;
                coada.push(node);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        ll a,b,c,p;
        cin>>a>>b>>c>>p;
        muchii[a].push_back({b,c,p});
        muchii[b].push_back({a,c,p});
    }
    for(int i=1;i<=n;i++)
        if(muchii[i].size())
        {
            sort(muchii[i].begin(),muchii[i].end(),bycul);
            ll suma=0;
            ll lg=0;
            for(int j=0;j<muchii[i].size();j++)
            {
                lg++;
                suma+=muchii[i][j].cost;
                if(j+1==muchii[i].size()||muchii[i][j+1].cul!=muchii[i][j].cul)
                {
                    /*if(lg==1)
                        muchii[i][j].cost=0;*/
                    if(suma-muchii[i][j].cost<muchii[i][j].cost)
                        muchii[i][j].cost=suma-muchii[i][j].cost;
                    lg=0;
                    suma=0;
                }
            }
        }
    bfs();
    cout<<dist[n];
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int j=0;j<muchii[i].size();j++)
      |                         ~^~~~~~~~~~~~~~~~~
Main.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<date>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |                 if(j+1==muchii[i].size()||muchii[i][j+1].cul!=muchii[i][j].cul)
      |                    ~~~^~~~~~~~~~~~~~~~~~

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