Submission #9187

#	Time	Username	Problem	Language	Result	Execution time	Memory
9187		shinhj88	Your life (kriii2_Y)	C++98	4 / 4	80 ms	7136 KiB

Y

#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 / 1
• Subtask 2: 3 / 3