[help] can't find the reason for TLE

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

my code

#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
inline void io(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
}
 
const int MAX_SIZE = 1e5+1;
 
vector<vector<pair<int,int>>> adjList(MAX_SIZE,vector<pair<int,int>>());
vector<map<int,int>> trav(MAX_SIZE,map<int,int>());
 
ll d[MAX_SIZE];
 
long long dijsktra(int n){
	int src = 1,dest = n;
	for(int i=0;i<=n;i++)d[i] = INT_MAX;
	d[src] = 0;
	priority_queue<pair<int,int>> q;
	q.push({0,src});
	while(!q.empty()){
		int v = q.top().second;
		int dis = q.top().first*-1;
		q.pop();
		if(v==n)return dis;
		if(d[v]<dis)continue;
		for(auto e : adjList[v]){
			int to = e.first;
			int len = e.second;
			int t = d[v];
			while(trav[v].find(t)!=trav[v].end())t++;
			t+=len;
			if(t < d[to]){
			//	q.erase({d[to],to});
				d[to] = t;
				q.push({-d[to],to});
			}
		}
	}
	if(d[n]==INT_MAX)d[n]=-1;
	return d[n];
}
 
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		adjList.at(a).push_back({b,c});
		adjList.at(b).push_back({a,c});
	}
	for(int i=0;i<n;i++){
		int k;
		scanf("%d",&k);
		while(k--){
			int t;
			scanf("%d",&t);
			trav.at(i+1).insert({t,1});
		}
	}
	printf("%d\n",dijsktra(n));
}

107892710

But it get TLE on test 66. It's just a dijsktra with a simple modification. I can't figure out a way to make this any more faster.

Here's another code i found from top of the standings. It's almost the same as mine but passes in a very small time. I've been comparing two codes but have no idea for a reason for TLE.

2276080

Can someone help me figure out the problem?

Thank you.

Comments (4)

Write comment?

king_of_tt

4 years ago, # |

← Rev. 2 →

Your solution is O(M * log(n) * log(q)), but AC solution is O(M * log(n)), try to cut excess logarithm

→ Reply

Lakshi4h

4 years ago, # ^ |

Oh i can move the small while loop outside of the for loop because i'm repeating the same thing. Couldn't see it even when i was comparing two codes ;-;

Thank you for your help

SummerSky

I also read your codes, and I am not quite sure but I think it is this line

'while(trav[v].find(t)!=trav[v].end())t++;'

that costs too much time. Perhaps you could move it outside the loop

'for(auto e : adjList[v])'

since the result keeps the same whatever element 'e' is.

Yes that's what i did to get it accepted. :D Thank you for the reply.

Lakshi4h's blog