Submission #9183

# Submission time Handle Problem Language Result Execution time Memory
9183 2014-09-28T04:26:29 Z shinhj88 Your life (kriii2_Y) C++
0 / 4
0 ms 3580 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));
                        }
                }
        }

}
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));

}
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 3580 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -