10816 - Travel in Desert

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

Here is test

Post by medv » Thu Jan 26, 2006 10:33 am

You are wrong on this test (presented here earlier):

3 3
1 3
1 2 10.0 10.0
1 2 11.0 9.0
2 3 11.0 10.0

Your answer is
1 2 3
20.0 11.0


The correct is

1 2 3
19.0 11.0

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

10816 I don't know my error

Post by ibroker » Mon May 01, 2006 5:11 am

I use union-set finding temperature and dijkstra finding length.
I use these algorithms many times at other problems.
But I only get WA in this problem.
I already correct answer all of input at board
What's the matter?

Code: Select all

#include <cstdio>
#include <vector>
#include <algorithm>

#define M 150

using namespace std;

struct ss
{
	int v1, v2;
	int length, temperature;

	ss(int a, int b, int c, int d)
	{
		v1 = a;
		v2 = b;
		temperature = c;
		length = d;
	}
};
bool cmp(ss d1, ss d2)
{
	return d1.temperature<d2.temperature;
}

const double eps = 1e-10;
int n, m;
int start, end;
vector<ss> data;
vector<int> print;
int edge[M][M];

int tem, dis;

int find(int, int[]);
int union_set(int, int);
int dijkstra(int, int);
int main()
{
	int a, b;
	double c, d;
	int i;
	while(scanf("%d %d", &n ,&m)==2)
	{
		scanf("%d %d", &start, &end);
		for(i=0; i<m; i++)
		{
			scanf("%d %d %lf %lf", &a, &b, &c, &d);
			data.push_back(ss(a, b, (int)(c*10+eps), (int)(d*10+eps)));
		}
		sort(data.begin(), data.end(), cmp);

		tem = union_set(start, end);
		dis = dijkstra(start, end);

		vector<int>::iterator ii;
		for(ii=print.begin(); ii!=print.end(); ++ii)
		{
			printf("%d ", (*ii));
		}
		printf("\n");
		printf("%.1lf %.1lf\n", dis/10. + eps, tem/10. + eps);

		print.clear();
		data.clear();
	}
	return 0;
}

int dijkstra(int s, int e)
{
	int distance[M], via[M];
	bool check[M];
	int i, j;
	int min, minj;

	distance[0]=9999999;
	for(i=1; i<=n; i++)
	{
		check[i] = false;
		via[i]=0;
		distance[i] = edge[e][i];
		if(distance[i]==0)
		{
			distance[i]=9999999;
		}
		else via[i] = e;
	}
	for(i=1; i<=n; i++)
	{
		min = 9999999; minj=0;
		for(j=1; j<=n; j++)
		{
			if(min>distance[j] && !check[j])
			{
				min = distance[j];
				minj = j;
			}
		}
		check[minj] = true;
		for(j=1; j<=n; j++)
		{
			if(distance[j]>distance[minj] + edge[minj][j] && !check[j] && edge[minj][j])
			{
				distance[j] = distance[minj] + edge[minj][j];
				via[j] = minj;
			}
		}
	}
	while(s!=e)
	{
		print.push_back(s);
		s = via[s];
	}
	print.push_back(e);
	return distance[start];
}

int union_set(int s, int e)
{
	vector<ss>::iterator ii;
	int parent[M];
	int t1, t2;
	int i, j;

	for(i=0; i<=n; i++){ for(j=0; j<=n; j++) edge[i][j]=0; }
	for(i=1; i<=n; i++) parent[i] = i;
	for(ii=data.begin(); ii!=data.end(); ++ii)
	{
		t1 = (*ii).v1;
		t2 = (*ii).v2;
		edge[t1][t2] = edge[t2][t1] = (*ii).length;
		t1 = find(t1, parent);
		t2 = find(t2, parent);
		if(t1!=t2)
		{
			parent[t1] = parent[t2];
		}

		if(find(s, parent) == find(e, parent))
		{
			if(ii+1 == data.end() || (*ii).temperature!=(*(ii+1)).temperature)
			{
				break;
			}
		}
	}
	return (*ii).temperature;
}

int find(int c, int parent[])
{
	if(c!=parent[c]) return find(parent[c], parent);
	else return c;
}

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Tue May 09, 2006 8:46 am

Hello, I solve this problem today.
And my method is sorting temperature and try every one of them to find the shortest path.

I have no idea how your method work, so I couldn't help you.
Sorry for that, but you could try my method.
That's easy right.

But could you describe your union_find method in more detail.
Maybe I could help you when I understand your method.

Lonely

ibroker
New poster
Posts: 18
Joined: Tue Nov 08, 2005 6:38 pm

My algorithm

Post by ibroker » Fri May 12, 2006 9:46 am

My method similar to you.
I also sort temperature and connect.
this means, If start and end point are same group(exist path),
then I try dijkstra algorithm.
I also connect every same temperature.
but I don't know why I got WA. plz help~~

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Thu May 18, 2006 12:31 pm

sorry I couldn't find your error.
could somebody help him, thanks a lot

but I think of using two dijkstra algorithm to solve this problem

first, using modified dijkstra algo to find out temperature
think about a little DP applied to dijkstra algo
then you would find out temperature in one dijkstra

and second, use temperature to find shortest path
that's all

hope this helps you

Lonely

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu May 18, 2006 1:31 pm

The above code doesn't handle the muliple edges right. For this input

Code: Select all

2 4
1 2
1 2 40.0 10.0
1 2 40.0 7.0
1 2 40.0 8.0
1 2 40.0 11.0 
it prints

Code: Select all

1 2
11.0 40.0
which is obviously wrong.

lonelyone
Learning poster
Posts: 65
Joined: Sat Feb 19, 2005 6:53 pm

Post by lonelyone » Fri May 19, 2006 3:12 pm

thanks to little joey..

you are the great guy..

thanks again

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Wed Jul 12, 2006 11:09 pm

For the Input:

Code: Select all

10 100 
1 10 
2 8 0.1 33.5 
10 5 35.9 27.9 
3 5 14.6 10.6 
2 8 49.2 36.2 
6 3 43.7 2.8 
2 5 15.4 30.3 
2 7 39.6 11.9 
8 7 3.9 37.2 
10 3 30.0 6.8 
6 5 31.2 30.4 
3 4 16.5 7.4 
4 9 14.5 34.8 
3 8 36.0 3.8 
4 2 27.9 33.0 
7 6 34.3 19.1 
9 7 44.3 24.1 
5 9 30.6 24.7 
1 10 35.1 37.1 
7 2 4.9 39.4 
10 4 45.5 8.5 
7 1 37.7 16.7 
2 9 44.0 14.5 
7 4 3.9 33.8 
9 3 4.2 13.0 
4 6 15.9 24.0 
5 1 30.7 37.8 
4 7 24.6 22.2 
5 3 33.0 27.1 
8 4 1.3 29.8 
7 1 13.7 36.2 
6 8 7.5 5.6 
2 3 15.1 15.1 
2 5 43.1 36.7 
8 2 33.8 0.8 
6 10 25.9 21.0 
2 9 44.7 2.3 
7 1 16.9 1.4 
1 2 15.6 36.3 
1 10 3.8 2.5 
9 4 4.2 39.6 
3 1 33.7 29.2 
5 1 2.2 19.7 
9 10 48.5 6.9 
2 5 50.0 5.4 
1 9 46.8 12.8 
9 4 48.4 24.9 
8 2 11.8 31.1 
4 5 11.7 31.0 
6 2 25.0 20.1 
10 7 30.4 39.9 
5 9 11.0 24.5 
10 3 48.6 39.6 
4 8 0.4 11.5 
9 1 11.9 25.9 
1 7 28.2 39.9 
10 9 15.8 1.0 
9 3 18.0 3.9 
1 8 19.2 35.9 
6 9 1.2 35.7 
3 5 5.6 27.3 
9 7 38.7 36.3 
6 4 14.3 27.0 
5 7 49.9 28.2 
3 2 20.0 2.2 
8 7 39.0 29.3 
6 3 1.1 20.1 
4 10 18.9 26.2 
2 10 42.4 5.6 
3 6 28.6 18.3 
9 7 25.8 21.8 
10 5 19.0 12.2 
7 10 19.3 36.9 
5 10 1.3 24.2 
6 1 25.4 11.9 
10 4 49.7 28.0 
8 10 43.8 15.0 
7 10 19.6 19.4 
8 7 10.6 28.7 
9 3 23.5 5.6 
5 2 17.2 11.7 
7 4 35.6 31.4 
6 4 30.9 11.3 
3 6 25.7 31.4 
2 9 48.3 4.7 
2 5 22.3 39.7 
10 2 45.1 33.6 
4 7 16.0 4.5 
3 10 2.5 5.4 
5 1 15.0 34.6 
7 4 2.3 7.5 
8 6 39.2 35.9 
3 6 41.5 7.8 
3 10 7.1 23.4 
9 8 27.1 17.4 
4 9 48.6 39.3 
3 1 12.8 1.4 
3 10 12.6 12.8 
4 5 47.3 22.4 
4 3 9.4 30.6 
6 2 14.3 9.3 
Why the answer posted is :

Code: Select all

1 5 10 
43.9 2.2 
i found

Code: Select all

1 10
2.5 3.8
can someone explain me this one?
I use one Dijkstra.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Jul 13, 2006 3:38 am

asif_rahman0, you probably have to look at the problem description again.....

btw, that input is not very correct, since we must have 20 <= R <= 50, but it shall not matter for most correct programs.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

Post by asif_rahman0 » Thu Jul 13, 2006 8:46 am

thnx Observer.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Wed Aug 02, 2006 9:57 pm

Please Helllllllllllllllp.
I use Kruskal first and get the MiniMax temperature and then iterating on all edges

Code: Select all

	int i;
	for(i=0;i<links;i++)
		if(e[i].t <= maxTemp && lenght[e[i].u][e[i].v] > e[i].w)
				lenght[e[i].v][e[i].u] = lenght[e[i].u][e[i].v] = e[i].w;
So i build my array and send it to dijkstra....I test every thing here all is right but i still got wa....please is this right..I need more tricky test case

Thanks in advance.
Sleep enough after death, it is the time to work.
Mostafa Saad

hamedv
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Re: 10816 - Travel in Desert

Post by hamedv » Fri Sep 05, 2008 8:13 pm

Hi
My Code Gives write answer too all test cases that i have tested.
but it gives run time error on some test cases. I tries to find the reason but i couldn't.
please help me. i use 2 Floyd-Warshal s to solve it

Code: Select all

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

#define foreach(i, c) for( __typeof( (c).begin() ) i = (c).begin(); i != (c).end(); ++i )
#define iterator(c) __typeof( (c).begin() )
#define all(c) c.begin(), c.end()
#define vecshoot(c) { int __i; foreach(__i, c) cerr << " " << (*__i) ; cerr << endl; }
#define error(n) cerr << #n << " = " << n << endl;

struct Node {
	double Temp, Dist;
	Node ( ) { }
	Node (double _Temp, double _Dist )
	{
		Temp = _Temp;
		Dist = _Dist;
	}
};

struct DNode {
	double Dist;
	vector<int> Path;
	DNode ( ) { }
	DNode (int a, int b, double _Dist)
	{
		Dist = _Dist;
		Path.clear();
		Path.push_back(a);
		Path.push_back(b);
	}
};

const int MAX_N = 100;
double INF = 1e7;

vector<Node> Nodes[MAX_N+1][MAX_N+1];
DNode DNodes[MAX_N+1][MAX_N+1];
double Temps[MAX_N+1][MAX_N+1];
double MinTemp;

bool HasWay(const DNode& a)
{
	return a.Dist != INF;
}

DNode DNodeCat(DNode& tmp, const DNode& a, const DNode& b)
{
	tmp.Dist = a.Dist + b.Dist;
	tmp.Path.clear();
	for (int i = 0; i < a.Path.size(); i++)
		tmp.Path.push_back(a.Path[i]);
	for (int i = 1; i < b.Path.size(); i++)
		tmp.Path.push_back(b.Path[i]);
}

int main()
{
	int E, N;
	while (cin >> N >> E)
	{
		for (int i = 0; i <= MAX_N; i++)
			for (int j = 0; j <= MAX_N; j++)
			{
				Temps[i][j] = INF;
				Nodes[i][j].clear();
				DNodes[i][j].Dist = INF;
				DNodes[i][j].Path.clear();
			}
		int FromNode, ToNode;
		cin >> FromNode >> ToNode;
		for (int i = 0; i < E; i++)
		{
			int X, Y;
			double R, D;
			scanf("%d %d %lf %lf", &X, &Y, &R, &D);
			Nodes[X][Y].push_back(Node(R, D));
			Nodes[Y][X].push_back(Node(R, D));
			Temps[X][Y] = Temps[Y][X] = min(Temps[X][Y], R);
		}
		for (int k = 1; k <= N; k++)
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= N; j++)
					if (Temps[i][k] != INF && Temps[k][j] != INF)
						Temps[i][j] = min(Temps[i][j], max(Temps[i][k], Temps[k][j]));
		MinTemp = Temps[FromNode][ToNode];
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (i != j)
				{
					double MD = INF;
					for (int k = 0; k < Nodes[i][j].size(); k++)
						if (Nodes[i][j][k].Temp <= MinTemp)
							if (Nodes[i][j][k].Dist < MD)
							MD = Nodes[i][j][k].Dist;
					Nodes[i][j].clear();
					DNodes[i][j].Dist = MD;
					DNodes[i][j].Path.reserve(MAX_N);
					DNodes[i][j].Path.clear();
					DNodes[i][j].Path.push_back(i);
					DNodes[i][j].Path.push_back(j);
				} else DNodes[i][j] = DNode(i, j, INF);
		for (int k = 1; k <= N; k++)
			for (int i = 1; i <= N; i++)
				for (int j = 1; j <= N; j++)
					if (HasWay(DNodes[i][k]) && HasWay(DNodes[k][j]))
						if (DNodes[i][k].Dist+DNodes[k][j].Dist < DNodes[i][j].Dist)
						{
							DNodeCat(DNodes[i][j], DNodes[i][k], DNodes[k][j]);
						}
		DNode res = DNodes[FromNode][ToNode];
		for (int i = 0; i < res.Path.size(); i++)
		{
			if (i)
				cout << " ";
			cout << res.Path[i];
		}
		cout << endl;
		printf("%.1f %.1f\n", res.Dist, MinTemp);
	}
	return 0;
}

my program gives runtime error in this part:

Code: Select all

		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (i != j)
				{
					double MD = INF;
					for (int k = 0; k < Nodes[i][j].size(); k++)
						if (Nodes[i][j][k].Temp <= MinTemp)
							if (Nodes[i][j][k].Dist < MD)
							MD = Nodes[i][j][k].Dist;
					Nodes[i][j].clear();
					DNodes[i][j].Dist = MD;
					DNodes[i][j].Path.reserve(MAX_N);
					DNodes[i][j].Path.clear();
					DNodes[i][j].Path.push_back(i);
					DNodes[i][j].Path.push_back(j);
				} else DNodes[i][j] = DNode(i, j, INF);

User avatar
sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

I got PE!!!

Post by sreejond » Wed Jun 17, 2009 7:59 am

Interestingly i got PE in this problem.
Can anybody plz check my code.
I cant found my bug. :(
Thnx in advance.

Code: Select all

#include<stdio.h>
#include<stdlib.h>

#define MAXN 102
#define INF 2147483647
#define max(a, b) (a>b?a:b)
#define min(a,b) (a>b?b:a)

struct ss 
{
	int u, v;
	double temp, dis;
};

ss Edge[MAXN*100];
int N, E, S, T;
double D[MAXN][MAXN];
double Tp[MAXN][MAXN];
int P[MAXN][MAXN];

void Ini() 
{
	int i, j;
	for(i = 1; i<= N; i++) 
	{
		for(j = 1; j<= N; j++) 
		{
			D[i][j] = Tp[i][j] = INF;
			P[i][j] = i;
		}
		D[i][i] = Tp[i][i] = 0;
	}
}

void ReadCase() 
{
	int i, u, v;
	double d, t;
	scanf("%d%d",&S,&T);
	for(i = 0; i<E; i++) 
	{
		scanf("%d%d%lf%lf",&u,&v,&t,&d);
		Edge[i].u = u;
		Edge[i].v = v;
		Edge[i].dis = d;
		Edge[i].temp = t;
		if(Tp[u][v] > t) 
		{
			Tp[u][v] = t;
			Tp[v][u] = t;
		}
	}
}


void GetTemp() 
{
	int i, j, k;
	for(k = 1; k<= N; k++) 
	{
		for(i = 1; i <= N; i++) 
		{
			for(j = 1; j<= N; j++) 
			{
				Tp[i][j] = min(Tp[i][j], max(Tp[i][k],Tp[k][j]));
			}
		}
	}
}

void GetDis(double lim) 
{
	int i, j, k;
	double dis;
	for(k = 1; k<= N; k++) 
	{
		for(i = 1; i <= N; i++) 
		{
			for(j = 1; j<= N; j++) 
			{
				dis = D[i][k] + D[k][j];
				if(D[i][j] > dis) 
				{
					D[i][j] = dis;
					P[i][j] = P[k][j];
				}
			}
		}
	}
}

void Set(double lim) 
{
	int i, u, v;
	for(i = 0; i<E; i++) 
	{
		u = Edge[i].u;
		v = Edge[i].v;
		if(D[u][v] > Edge[i].dis && Edge[i].temp<=lim) 
		{
			D[u][v] = D[v][u] = Edge[i].dis;
		}
	}
}

void Print(int u, int v) 
{
	if(u == v)
		printf("%d",v);
	else 
	{
		Print(u,P[u][v]);
		printf(" %d",v);
	}
}

void Cal() 
{
	double Limit;
	GetTemp();
	Limit = Tp[S][T];
	Set(Limit);
	GetDis(Limit);
	Print(S,T);
	printf("\n");
	printf("%.1lf %.1lf\n",D[S][T],Tp[S][T]);
}

int main() 
{
	while(scanf("%d%d",&N,&E) == 2) 
	{
		Ini();
		ReadCase();
		Cal();
	}
	return 0;
}


User avatar
sreejond
New poster
Posts: 32
Joined: Fri May 23, 2008 6:16 pm
Contact:

Re: 10816 - Travel in Desert

Post by sreejond » Fri Jun 19, 2009 11:42 am

Is there no one to help me???!!!

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 10816 - Travel in Desert

Post by Jehad Uddin » Sat Feb 20, 2010 3:14 pm

getting wa in this prob pls help,

Code: Select all

#include<iostream>
#include<stdlib.h>
#include<string>
#include<queue>
#include<map>
#include<vector>
#define INF 900000000
using namespace std;
struct xx
{
    int u,v;
    int D,R;
};

xx X[10005];
int n,e;
int p[200],rank[200];
int path[200];
int dis[200];
int color[200];
int S,T;
int tt,st;
int tmp[200];
struct ss
{
    int pos;
    int R,D;
};


vector<ss>edge[200];
class comp
{
    public : bool operator()(const ss &a,const ss &b)
    {
        return a.D>b.D;
    }
};

priority_queue<ss,vector<ss>,comp>Q;

int cmp(const void *a,const void *b)
{
    xx *x=(xx *)a;
    xx *y=(xx *)b;
    if(x->R>y->R) return 1;
    else if(x->R<y->R) return -1;
    else
    {
        if(x->D>y->D) return 1;
        else if(x->D<y->D) return -1;
        else return 0;
    }
}

void ini()
{
    int i,j,k;
    for(i=0;i<=n;i++)
    {
        path[i]=i,p[i]=i,rank[i]=0,edge[i].clear(),dis[i]=INF,color[i]=0,tmp[i]=0;
    }
    while(!Q.empty()) Q.pop();
    tt=0,st=0;
}

int find(int y)
{
    if(y!=p[y]) p[y]=find(p[y]);
    return p[y];
}

void link(int x,int y)
{
    if(rank[x]>rank[y])
    {
        p[y]=x;
    }
    else
    {
        if(rank[x]==rank[y]) rank[y]++;
        p[x]=y;
    }
}


void mst()
{
    int i,j,k,l,u,v,w,z;
    ss s1,s2;
    qsort(X,e,sizeof(xx),cmp);
    j=0;
    l=0;
    for(i=0;i<e;i++)
    {
        u=X[i].u,v=X[i].v;
        w=find(u),z=find(v);
        if(w!=z&&find(S)!=find(T))
        {
            link(w,z);
            j++;
            s1.D=X[i].D,s1.R=X[i].R;
            s1.pos=v;
            edge[u].push_back(s1);
            s1.pos=u;
            edge[v].push_back(s1);
            if(find(S)==find(T)) l=X[i].R,st=X[i].R;
            //printf("%d %d %d\n",u,v,l);

        }
        else if(find(S)!=find(T))
        {
            s1.D=X[i].D,s1.R=X[i].R;
            s1.pos=v;
            edge[u].push_back(s1);
            s1.pos=u;
            edge[v].push_back(s1);
            //printf("%d %d %d\n",u,v,l);
        }
        else if(find(S)==find(T)&&X[i].R<=st)
        {
            s1.D=X[i].D,s1.R=X[i].R;
            s1.pos=v;
            edge[u].push_back(s1);
            s1.pos=u;
            edge[v].push_back(s1);
            printf("%d %d %d\n",u,v,l);
        }

        //else if(find(S)==find(T)&&X[i].R>l) break;




    }
}

int reach(int u)
{
    int i,j,v;
    ss s1,s2;
    if(u==T)
    {

        return 1;
    }
    for(i=0;i<edge[u].size();i++)
    {
        s1=edge[u][i];
        v=s1.pos;
        if(color[v]==0)
        {
            color[v]=1;
            if(reach(v))
            {
                if(s1.R>st) st=s1.R;
                tt+=s1.D;
                path[v]=u;
                return 1;
            }
        }
    }
    return 0;

}
void print(int u)
{
    if(u==S) printf("%d",u);
    else
    {

        print(path[u]);
        printf(" %d",u);
    }
}

void dijk()
{
    int i,j,k,l,u,v;
    ss s1,s2,s3;
    s1.pos=S;
    s1.D=0,s1.R=0;
    Q.push(s1);
    while(!Q.empty())
    {
        s1=Q.top();
        Q.pop();
        u=s1.pos;
        if(u==T) st=s1.R,tt=s1.D;
        for(i=0;i<edge[u].size();i++)
        {
            s2=edge[u][i];
            v=s2.pos;
            if(s1.D+s2.D<dis[v])
            {
                dis[v]=s1.D+s2.D;
                path[v]=u;
                if(s2.R>s1.R) s3.R=s2.R;
                else s3.R=s1.R;
                s3.D=dis[v];
                s3.pos=v;
                Q.push(s3);
            }
        }
    }

}

int parse(char *str1)
{
    int i,j=0;
    for(i=0;i<strlen(str1)&&str1[i]!='.';i++)
    {
        j=j*10+str1[i]-48;
    }
    j=j*10;
    if(i!=strlen(str1)&&str1[i]=='.')
    {
        i++;
        if(i<strlen(str1)) j+=str1[i]-48;
    }
    return j;
}

int main()
{
    int i,j,k,l,u,v;
    char str1[40],str2[40];
   // freopen("D:\\10816.txt","wt",stdout);
    while(scanf("%d%d",&n,&e)==2)
    {
        ini();
        scanf("%d%d",&S,&T);
        for(i=0;i<e;i++)
        {
            scanf("%d%d",&X[i].u,&X[i].v);
            scanf("%s%s",&str1,&str2);
            //cin>>str1>>str2;
            //X[i].R=u*10+v;
            X[i].R=parse(str1);
            //scanf("%d.%d",&u,&v);
            //X[i].D=u*10+v;
            X[i].D=parse(str2);

        }
        mst();
        dijk();


        print(T);
        printf("\n");
        printf("%d.%d %d.%d\n",tt/10,tt%10,st/10,st%10);
    }
    return 0;
}

Post Reply

Return to “Volume 108 (10800-10899)”