oj.uz

Submission #554373

# Submission time Handle Problem Language Result Execution time Memory
554373 2022-04-28T09:38:33 Z andrei_boaca Robot (JOI21_ho_t4) C++17
0 / 100
 137 ms 15128 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Incorrect 3 ms 2772 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 8872 KB Output is correct
2 Correct 20 ms 5368 KB Output is correct
3 Correct 67 ms 13364 KB Output is correct
4 Correct 31 ms 6868 KB Output is correct
5 Incorrect 137 ms 15128 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2644 KB Output is correct
9 Incorrect 3 ms 2772 KB Output isn't correct
10 Halted 0 ms 0 KB -