oj.uz

Submission #9187

# Submission time Handle Problem Language Result Execution time Memory
9187 2014-09-28T04:27:51 Z shinhj88 Your life (kriii2_Y) C++
4 / 4
 80 ms 7136 KB 
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
vector<int > G[100001];
int n,m;
int dijkstra(int s,int t)
{
        priority_queue<pair<int,int> > pq;
        pq.push(make_pair(0,s));
        vector<int> dist(n + 1, 987654321);
        dist[s] = 0;
        while(!pq.empty())
        {
                int v = pq.top().second,cost = -pq.top().first;
                pq.pop();
                if(dist[v] < cost)continue;
                for(int i = 0; i < G[v].size(); i++)
                {
                        int u = G[v][i], nextcost = cost + 1;
                        if(dist[u] > nextcost)
                        {
                                dist[u] = nextcost;
                                if(u == t)return nextcost;
                                pq.push(make_pair(-nextcost,u));
                        }
                }
        }
        return -1;

}
int main()
{
        scanf("%d%d",&n,&m);
        while(m--)
        {
                int a,b;
                scanf("%d%d",&a,&b);
                G[a].push_back(b);
        }
        printf("%d\n",dijkstra(1,n));

}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3580 KB Output is correct
2 Correct 0 ms 3580 KB Output is correct
3 Correct 0 ms 3580 KB Output is correct
4 Correct 0 ms 3580 KB Output is correct
5 Correct 0 ms 3580 KB Output is correct
6 Correct 0 ms 3580 KB Output is correct
7 Correct 0 ms 3580 KB Output is correct
8 Correct 0 ms 3580 KB Output is correct
9 Correct 0 ms 3580 KB Output is correct
10 Correct 20 ms 4116 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3968 KB Output is correct
2 Correct 40 ms 7004 KB Output is correct
3 Correct 56 ms 7004 KB Output is correct
4 Correct 48 ms 7004 KB Output is correct
5 Correct 52 ms 7004 KB Output is correct
6 Correct 48 ms 7004 KB Output is correct
7 Correct 28 ms 7004 KB Output is correct
8 Correct 80 ms 7136 KB Output is correct
9 Correct 52 ms 7004 KB Output is correct
10 Correct 76 ms 6740 KB Output is correct