OJ Board

Code: Select all

void main()
{
	int i;
   for(i = 0; i < 2147483647; ++i)
   	;
}

Code: Select all

#include <stdio.h>
#include <string.h>
#include <ctype.h>

struct
{
	int adj;
	int d;
} list[1009][1009];

int n, n_adj[1009], dist[1009], memory[1009];
bool visited[1009];

int extractMin()
{
	int i, min = 2147483646, index = -1;
	for(i = 0; i < n; ++i)
		if(visited[i] == false && dist[i] != -1 && dist[i] < min)
		{
			min = dist[i];
			index = i;
		}
	return index;
}

void dijkstra()
{
	int i, u, v;
	memset(dist, -1, sizeof(dist));
	memset(visited, false, sizeof(visited));
	dist[0] = 0;
	for(;;)
	{
		u = extractMin();
		if(u != -1)
			visited[u] = true;
		else
			break;
		for(i = 0; i < n_adj[u]; ++i)
		{
			v = list[u][i].adj;
			if(visited[v] == false && (dist[v] == -1 || dist[v] > dist[u] + list[u][i].d))
				dist[v] = dist[u] + list[u][i].d;
		}
	}
}

int n_path(int u)
{
	if(u == 0)
		return 1;
	if(memory[u] != -1)
		return memory[u];
	int i, count = 0, v;
	for(i = 0; i < n_adj[u]; ++i)
	{
		v = list[u][i].adj;
		if(dist[v] != -1 && dist[v] == dist[u] - list[u][i].d)
			count += n_path(v);
	}
	return memory[u] = count;
}

bool exit(char s[], int &m)
{
	int i, count = 0, prev = ' ';
	for(i = 0; s[i]; ++i)
	{
		if(isdigit(s[i]) && !isdigit(prev))
			++count;
		prev = s[i];
	}
	if(count == 1)
	{
		sscanf(s, "%d", &n);
		if(n == 0)
			return true;
	}
	else if(count == 2)
	{
		sscanf(s, "%d%d", &n, &m);
		return false;
	}
	else
		n /= 0;
	return false;
}

void main()
{	
	int m, x, y, d;
	char s[100];
	for(;;)
	{
		scanf(" %[^\n]", s);	
		if(exit(s, m))
			break;
		memset(n_adj, 0, sizeof(n_adj));
		while(m--)
		{
			scanf("%d%d%d", &x, &y, &d);		
			--x;
			--y;
			list[x][n_adj[x]].adj = y;
			list[x][n_adj[x]++].d = d;
			list[y][n_adj[y]].adj = x;
			list[y][n_adj[y]++].d = d;
		}
		dijkstra();
		memset(memory, -1, sizeof(memory));
		printf("%d\n", n_path(1));
	}
}

Code: Select all

cut after AC

Code: Select all

6 11
1 6 2995
6 3 4827
3 1 32391
1 3 153
3 5 12382
5 4 18716
4 3 19895
3 6 21726
6 1 1869
1 5 25667
5 2 17035
10 8
1 4 16803
4 8 6286
8 1 28531
1 10 10722
10 3 22946
3 8 24230
8 6 30570
6 2 19832
0

Code: Select all

3
2

Code: Select all

#include <stdio.h>
#include <vector>
#include <queue>
#include <functional>
#include <string.h>

using namespace std;

#define MAXN	1005
#define INF		999999999

typedef struct node_
{
	int u,cost;
} node_;

bool operator < (node_ a,node_ b){ return a.cost > b.cost; }
bool operator > (node_ a,node_ b){ return a.cost < b.cost; }
bool operator == (node_ a,node_ b){ return a.cost == b.cost; }

int v,E;
vector <node_> adj[MAXN];
vector <int> newAdj[MAXN];
int d[MAXN],path[MAXN];
bool visited[MAXN];
priority_queue <node_> PQ;


void dijkstra(int s)
{
	int i;
	node_ u,next;

	for( i = 1; i <= v; i++ )
	{
		d[i] = INF;
		visited[i] = false;
	}

	d[s] = 0;
	u.u = s,u.cost = 0;
	while(!PQ.empty()) PQ.pop();
	PQ.push(u);

	while(!PQ.empty())
	{
		u = PQ.top();
		PQ.pop();

		if( visited[u.u] ) continue;
		visited[u.u] = true;

		for( i = 0; i < adj[u.u].size(); i++ )
		{
			next = adj[u.u][i];

			if( !visited[next.u] )
			{
				if( d[next.u] > d[u.u] + next.cost )
				{
					d[next.u] = d[u.u] + next.cost;
					PQ.push(next);
				}
			}
		}

	}
}

void rebuildGraph()
{
	int i,j;
	node_ u;

	for( i = 1; i <= v; i++ )
	{
		newAdj[i].clear();
		for( j = 0; j < adj[i].size(); j++ )
		{
			u = adj[i][j];
			if( d[i] > d[u.u] ) newAdj[i].push_back(u.u);
		}
	}
}

void countPath()
{
	int i,u,next;
	queue <int> Q;
	memset(visited,false,sizeof(visited));
	memset(path,0,sizeof(path));
	path[1] = 1,visited[1] = true;
	Q.push(1);

	while(!Q.empty()) 
	{
		u = Q.front();
		Q.pop();

		for( i = 0; i < newAdj[u].size(); i++ )
		{
			next = newAdj[u][i];
			if( !visited[next] )
			{
				visited[next] = true;
				path[next] = path[u];
				Q.push(next);
			}
			else path[next] += path[u];
		}
	}
}


int main()
{
	int i,m,n,w;
	node_ push;

	while(scanf("%d",&v) == 1 && v)
	{
		scanf("%d",&E);

		for( i = 1; i <= v; i++ ) adj[i].clear();

		for( i = 0; i < E; i++ )
		{
			scanf("%d %d %d",&m,&n,&w);
			push.u = n;push.cost = w;
			adj[m].push_back(push);push.u = m;
			adj[n].push_back(push);
		}

		dijkstra(2);
		rebuildGraph();
		countPath();
		printf("%d\n",path[2]);
	}

	return 0;
}

Code: Select all

int f(int u)
{
	int cnt=0,v;
	if(u==2)
		return 1;
	if(ct[u]>=0)
		return ct[u];
	for(v=1;v<=n;v++)
		if(mat[v][u]<inf && dist[v]<dist[u])
			cnt+=f(v);
	ct[u]=cnt;
	return ct[u];
}

Code: Select all

6 9 
1 6 2995 
6 3 4827 
3 1 32391  
3 5 12382 
5 4 18716 
4 3 19895  
6 1 1869 
1 5 25667 
5 2 17035