Submission #9187

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
9187	2014-09-28 04:27:51	shinhj88	Your life (kriii2_Y)	C++98	4 / 4	80 ms	7136 KiB

Y

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3