10449 - Traffic

[Mukit Chowdhury]

Got TLE... Help please...

Code: Select all

Accepted... :) 

[lbv]

Got TLE... Help please...

The method you use to read input:

Code: Select all

      while(~scanf("%d",&n))

is interesting, but it gets the program stuck in an infinite loop if the input happens to contain strange characters at the end of the file, which apparently is the case for this problem. You could try instead:

Code: Select all

      while(scanf("%d",&n) == 1)

Also try the following case:

Input

Code: Select all

15 5 19 16 15 5 1 2 8 6 11 2 1 6 11 18
16
13 1
13 14
1 11
6 12
8 1
9 3
15 2
13 6
13 15
7 14
15 14
8 13
6 14
15 1
9 14
14 12
15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Output

Code: Select all

Set #1
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?

[Mukit Chowdhury]

The method you use to read input:

Code: Select all

      while(~scanf("%d",&n))

is interesting, but it gets the program stuck in an infinite loop if the input happens to contain strange characters at the end of the file, which apparently is the case for this problem. You could try instead:

Code: Select all

      while(scanf("%d",&n) == 1)

I tried with

Code: Select all

    while(scanf("%d",&n) != EOF)

but it also failed... and gave me same verdict... :/
what kind of strange character can appear in end of file ??? would you please give me a example ??? it will really help....
And your test case is really good... I should have thought about that facts.... :/ >:(

[lbv]

I tried with (..)
but it also failed... and gave me same verdict... :/
what kind of strange character can appear in end of file ??? would you please give me a example ??? it will really help....

Anything that doesn't conform to what scanf understands as an integer would cause the problem.

EOF will be returned by scanf if the end of file is reached before doing the first conversion (successful or not). If however, the end of file is not reached, but the first conversion fails, then scanf will return zero.

For example, if the input for this problem is:

Code: Select all

5 6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5

Then in the second iteration of the loop, scanf would return EOF, because there's nothing left to read.

If, on the other hand, the input is something like:

Code: Select all

5 6 7 8 9 10
6
1 2
2 3
3 4
1 5
5 4
4 5
2
4
5
A

Then it returns zero on the second iteration; the "A" can't be read into an int, scanf stops at that point and returns the number of matches so far, which is zero.

It is a little tricky, but it is not difficult to avoid this type of problems. The cleanest and most robust way to read data with scanf is, I think, to always compare its return value with the number of variables you're expecting to read.

[Mukit Chowdhury]

Humm... Thanks...
But the question is, as the problem statement says,

Code: Select all

The first line of each test case contains n (the number of junctions, 0 <= n <= 200) 

then why there will be input like 'A' ??? :/
It's first time, I've got TLE for this kind of reason.... :/

'A' can't be number of junction, right ???
Anyway, thanks again...

[brianfry713]

You deleted your full code so I can't try to explain why it wasn't working before.

[Mukit Chowdhury]

The code given below is my AC code. Here I've taken input using

Code: Select all

while(scanf("%d",&n)==1)

but when I used

Code: Select all

while(~scanf("%d",&n))

or

Code: Select all

while(scanf("%d",&n)!=EOF)

I got the verdict TLE !!! It astonished me, as it had never happened before with me.... Without this change, my full code is same... :O

Code: Select all

Deleted...

Sorry for late reply... I've not checked mail...

[brianfry713]

Yes it appears that the judge's input does not conform to the problem statement. There is a non-digit char after the last input. It is always safer to use the "while(scanf("%d", &n) == 1) {" style.

[Mukit Chowdhury]

Yes it appears that the judge's input does not conform to the problem statement. There is a non-digit char after the last input.

Though it sounds strange according to problem statement... anyway... Thanks for ensuring me about non digit character of the last input...

[LazyTym]

Help!!
i can not understand the problem statement.........Can anyone help me to understand this problem ?????????

thanks in advance

[brianfry713]

You can solve it using the Floyd-Warshall algorithm.

[nada_elnokaly]

I am getting WA
I used Bellman Ford to get the minimum distance +check if there's -ve cycles + handling the nodes that are not connected with the node 0 , also using while(scanf()==1){}

I think I handled most of the bugs discussed here and passes all the testcases that are posted here

I need help please

my code:

Code: Select all

#include <bits/stdc++.h>
using namespace std;
const int INF=100000000;
int cost[505],weight[505][505],dist[505],inCycle[505];
vector<int>adj[505];
int main(){
	int n,r,a,b,t=0;
	while(scanf("%d",&n)==1){
		t++;
		for(int i=0;i<n;i++){
			scanf("%d",&cost[i]);
			adj[i].clear();
		}
	
		scanf("%d",&r);

		for(int i=0;i<r;i++){
			scanf("%d%d",&a,&b);
			a--; b--;
			adj[a].push_back(b);
			weight[a][b]=(cost[b]-cost[a])*(cost[b]-cost[a])*(cost[b]-cost[a]);
		}
		
		for(int i=0;i<n;i++)dist[i]=INF;
		dist[0]=0;
		for(int k=0;k<n;k++)
			for(int i=0;i<n;i++)
				for(int j=0;j<(int)adj[i].size();j++){
					int u=i,v=adj[i][j];
					if(dist[u]==dist[v] && dist[u]==INF)continue;
					
					dist[v]=min(dist[v],dist[u]+weight[u][v]);
				
				}
		
		
		memset(inCycle,0,sizeof inCycle);
		for(int i=0;i<n;i++)
			for(int j=0;j<(int)adj[i].size();j++){
				int u=i,v=adj[i][j];
				if(dist[u]+weight[u][v]<dist[v]){
					inCycle[v]=1;
				}
			}
		int q;
		printf("Set #%d\n",t);
	
		scanf("%d",&q);
		for(int i=0;i<q;i++){
			scanf("%d",&a);
			a--; 
			if(dist[a]<3 || inCycle[a] || dist[a]==INF)printf("?\n");
			else printf("%d\n",dist[a]);
		}			
		
	}
	return 0;
}

[brianfry713]

There is probably an issue with the way you find negative cycles. Read this thread for ideas, or use the Floyd-Warshall algorithm.

[amp15]

My code passed all the test cases of UDebug....Still getting WA !! Please help anyone

Code: Select all

#include <bits/stdc++.h>

#define ms(a,b)         memset(a,b,sizeof(a))
#define pb(a)           push_back(a)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define ff              first
#define ss              second
#define sz(x)           x.size()
#define qu              queue
#define pqu             priority_queue
#define vc              vector
#define vi              vector<int>
#define vll             vector<long long>
#define pii             pair<int,int>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define all(x)          x.begin(),x.end()
#define CIN             ios_base::sync_with_stdio(0); cin.tie(0)
#define loop0(i,n)      for(int i=0;i<n;i++)
#define loop1(i,n)      for(int i=1;i<=n;i++)
#define stlloop(x)     for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define gcd(a, b)       __gcd(a, b)
#define lcm(a, b)       ((a)*((b)/gcd(a,b)))
#define case(z,x)       cout<<"Case "<<i<<": "<<x<<endl
#define case(z)         cout<<"Case "<<z<<": "
#define PI              3.14159265358979323846264338328
#define valid(tx,ty)    tx>=0 && tx<r && ty>=0 && ty<c
#define MAX             300
#define inf             10000000

/*---------------------------Graph Moves-----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------------------------*/

using namespace std;

int dis[MAX],parent[MAX];
vector<int>gu,gv,cost;
int node,edge;
map <int, int> mp;

bool bellman_ford()
{
    loop0(i,MAX)
    {
        dis[i]=inf;
    }
    dis[1]=0;
    loop1(i,node)
    {
        bool change=0;
        loop0(j,edge)
        {
            int u=gu[j];
            int v=gv[j];
            if(dis[u]+cost[j]<dis[v])
            {
                change=1;
                dis[v]=dis[u]+cost[j];
            }
        }
        if(change==0) return 1;
    }
}

int main()
{
    CIN;
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int n_cost,t;
    t=0;
    while(cin>>node)
    {
        //cout<<endl;
        t++;
        loop1(i,node)
        {
            cin>>n_cost;
            mp[i]=n_cost;
        }
        cin>>edge;
        loop0(i,edge)
        {
            int from,to,w;
            cin>>from>>to;
            gu.pb(from);
            gv.pb(to);
            w=mp[to]-mp[from];
            cost.pb(w*w*w);
        }
        int q,n;
        cin>>q;
        cout<<"Set #"<<t<<endl;
        int a=bellman_ford();
        loop0(i,q)
        {
            cin>>n;
            if(dis[n]<3 || dis[n]>100000)
            {
                cout<<"?"<<endl;
            }
            else
            {
                cout<<dis[n]<<endl;
            }
        }
        gu.clear();
        gv.clear();
        cost.clear();
        mp.clear();
    }
    return 0;
}