NEED HELP ON PLANETS(229 B)

Правка en1, от javacoder1, 2015-12-17 00:32:15

Hey i am getting tle on test 66. My code: Please anyone suggest any optimization MY CODE:

include<bits/stdc++.h>

using namespace std; typedef long long ll; int n,m;

define set1 pair<ll,int>

define dist first

define node second

define mp(a1,b1) make_pair(a1,b1)

vectorv[100005]; vectorarrive[100005];bool visited[100005]; ll get_num(int node,ll time) { int pos=(int)(lower_bound(arrive[node].begin(),arrive[node].end(),time)-arrive[node].begin()); while(pos<(int)arrive[node].size() && arrive[node][pos]==time) { pos++;time++; } return time; } ll path() { priority_queue< set1,vector,greater >pq; pq.push(mp(get_num(1,0),1)); while(!pq.empty()) { set1 temp=pq.top();pq.pop(); if(temp.node==n) return temp.dist; if(visited[temp.node]) continue; visited[temp.node]=true; for(int i=0;i<v[temp.node].size();i++) { set1 to=v[temp.node][i]; if(visited[to.node]) continue; ll distance=to.dist; if(to.node==n) { pq.push(mp(temp.dist+distance,to.node));continue; } pq.push(mp(get_num(to.node,temp.dist+distance),to.node)); } } return -1; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n>>m; memset(visited,false,sizeof visited); for(int i=0;i<m;i++) { int a,b;ll c;cin>>a>>b>>c; v[a].push_back(mp(c,b)); v[b].push_back(mp(c,a)); } for(int i=1;i<=n;i++) { int k;cin>>k; for(int j=1;j<=k;j++) { ll val;cin>>val; arrive[i].push_back(val); } } cout<<path()<<"\n"; return 0; }

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский javacoder1 2015-12-17 00:34:43 0 (published)
en2 Английский javacoder1 2015-12-17 00:33:11 1755 (saved to drafts)
en1 Английский javacoder1 2015-12-17 00:32:15 1886 Initial revision (published)