OJ Board

Code: Select all

#include <iostream>
using namespace std; 
#include <cstdio> 
#include <cstring> 

#define MAXV 100
#define MAXDEGREE 100
#define MAXINT 99999

int parent[MAXV];
int del[MAXV][MAXV];
int cas=1;

typedef struct
{
	int v;
	int weight;
}edge;

typedef struct
{
	edge edges[MAXV+1][MAXDEGREE];
	int degree[MAXV+1];
	int nvertices;
}graph;

void init(graph *g,int n)
{
	int i,j;
	int x,y,z;
	for(i=1;i<=MAXV;i++)
		g->degree[i]=0;
	g->nvertices=n;
	for(i=1;i<=g->nvertices;i++)
	{
		cin>>z;
		for(j=0;j<z;j++)
		{
			cin>>x>>y;
			del[i][x]=y;
			g->edges[i][g->degree[i]].v=x;
			g->edges[i][g->degree[i]].weight=y;
			g->degree[i]++;
		}
	}
}

void dijkstra(graph *g,int start)
{
	int i;
	bool intree[MAXV];
	int distance[MAXV];
	
	int v;
	int w;
	int weight;
	int dist;

	for(i=1;i<=g->nvertices;i++)
	{
		intree[i]=false;
		distance[i]=MAXINT;
		parent[i]=-1;
	}
	distance[start]=0;
	v=start;

	while(intree[v]==false)
	{
		intree[v]=true;//把结点v放入树中
		for(i=0;i<g->degree[v];i++)//有几个相临结点
		{
			w=g->edges[v][i].v;//与结点v相邻的结点
			weight=g->edges[v][i].weight;//到该结点的权重
			if( distance[w]>(distance[v]+weight)  )
			{
				distance[w]=distance[v]+weight;
				parent[w]=v;
			}
		}
		v=1;
		dist=MAXINT;
		for(i=2;i<=g->nvertices;i++)
		{
			if( (intree[i]==false) && (dist>distance[i]) )
			{
				dist=distance[i];
				v=i;
			}
		}
	}
}

void output(graph *g,int start,int end)
{
	int delay;
	int te;
	int pass[MAXV];
	int realpass[MAXV];
	int i,j,k;
	te=end;
	delay=0;
	i=0;
	k=0;
	realpass[k++]=start;
	while(parent[end]!=start)
	{
		pass[i++]=parent[end];
		end=parent[end];
	}
	for(j=i-1;j>=0;j--)
	{
		realpass[k++]=pass[j];
	}
	realpass[k]=te;
	cout<<"Case "<<cas++<<": Path = ";
	for(i=0;i<k;i++)
	{
		cout<<realpass[i]<<" ";
		delay+=del[realpass[i]][realpass[i+1]];
	}
	cout<<realpass[i]<<"; "<<delay<<" second delay"<<endl;
}

int  main() 
{ 
	graph g;
	int n;
	int i;
	int start,end;
	while(cin>>n&&n!=0)
	{
		init(&g,n);
		cin>>start>>end;
		dijkstra(&g,start);
		output(&g,start,end);
	}
    return 0; 
} 

Code: Select all

3
1 2 5
1 3 5
1 1 5
1 1
0

Code: Select all

Case 1: Path = 1; 0 second delay

Code: Select all

Remove After Accepted

Code: Select all

void show(type i,type j,type path[range][range])
{
if(i!=j) show(i,path[i][j],path);
printf(" %ld",j+1);
} 

Code: Select all

void floyd_warshall_spath(dtype graph[range][range],dtype path[range][range],type n)
{
type i,j,k;

for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)
if((graph[i][k]+graph[k][j])<graph[i][j])
   {   path[i][j]=path[k][j];   graph[i][j]=graph[i][k]+graph[k][j]; }
} 

Code: Select all

#include<stdio.h>
long G[12][12];
long x[15],ans[15];
long mincost,step;
void bfs(long s,long k,long N,long d)
{
	int i,sum = 0;
	
	x[k] = s;
	for(i = 1;i<=k;i++)
		sum += G[x[i-1]][x[i]];
	if(sum>mincost)
		return;
	
	if(s == d)
	{
		for(i = 0; i<=k ;i++)
			ans[i] = x[i];
		mincost = sum;
		step = k;
	}
	else
	{
		
		for(i = 1;i<=N;i++)
			if(G[s][i])
				bfs(i,k+1,N,d);
	}
}
main()
{
	long N,P,n,p,dest,start,test=1;
	//freopen("c:\in.txt","r",stdin);
	while(1)
	{
		scanf("%ld",&N);
		if(N == 0)
			break;

		for(n = 1;n<=N;n++)			for(p = 1;p<=N;p++)				G[n][p] = 0;
		mincost = 2147483647;
		for(n = 1;n<=N;n++)
		{
			
			scanf("%ld",&P);
			for(p = 1;p<=P;p++)	
			{
				scanf("%ld",&dest);
				scanf("%ld",&G[n][dest]);			
			}			
		}
		scanf("%ld%ld",&start,&dest);

		bfs(start,0,N,dest);
		printf("Case %ld: Path =",test++);
		for(p = 0;p<=step;p++)
			printf(" %ld",ans[p]);
		printf("; %ld second delay\n",mincost);
	}
	return 0;
}

Code: Select all

Removed after AC

Code: Select all

//non stop travel
#include<iostream>
using namespace std;
int arr[10][10];
void process(int,int,int);
void print(int[],int);
int main(){
	int n;
	int count=1;
	while(cin>>n){
		if(n==0) return(0);
		int i=0,j=0;
		while(i<n){
			j=0;
			while(j<n) arr[i][j++]=100000000;
			i++;
		}
		i=0;
		while(i<n){
			int k;
			cin>>k;
			while(k>0){
				int a,b;
				cin>>a>>b;
				arr[i][a-1]=b;
				k--;
			}
			i++;
		}
		int source,desti;
		cin>>source>>desti;
		//process
		cout<<"Case "<<count++<<": ";
		process(source-1,desti-1,n);
	}
}
void process(int s,int de,int l){
	int ar[10];
	int mark[10];
	int prev[10];
	int i=0;
	while(i<l){
		ar[i]=100000000;
		mark[i++]=0;
	}
	ar[s]=0;
	mark[s]=1;
	int mins=s;
	int loop=1;
	while(loop<l){
		//set accordin to mins
		int j=0;
		int min=100000000,minin;
		while(j<l){
			int d=arr[mins][j]+ar[mins];
			if(mark[j]==0){
				if(ar[j]>d) {
					ar[j]=d;
					prev[j]=mins;
				}
				if(ar[j]<min) {min=ar[j];minin=j;}
			}
			j++;
		}
		mins=minin;
		mark[mins]=1;
		loop++;
	}
	string path="";
	int r=de;
	while(r!=s){
		path=char(r+'1')+path;
		path=" "+ path;
		r=prev[r];
	}
	path=char(s+'1')+path;
	cout<<"Path = "<<path<<"; "<<ar[de]<<" second delay"<<"\n";
	return;
}
void print(int a[],int len){
	int i=0;
	while(i<len) cout<<a[i++]<<" ";
	cout<<"\n";
	return;
}

Code: Select all

#include <iostream>
#include <list>
#include <stdio.h>

using namespace std;

int main(int argc, char **argv)
{
	int cases = 1, nvert;
	
inicio:
	cin >> nvert;
	if(nvert == 0)
		return 0;
	
	
	int vet[11][11];
	

	// zerar caminhos
	for(int i = 0; i < 11; i++)
	{
		for(int x = 0; x < 11; x++)
		{
			vet[i][x] = 50001;
		}
	}
	
	int path[11];
	for(int i = 0; i < 11; i++)
		path[i] = -1;
	
	int dist[11];
	for(int i = 0; i < 11; i++)
		dist[i] = 50001;
	
	int to, from, numlig;
	int delay;
	

	// entrada
	for(int i = 1; i <= nvert; i++)
	{
		cin >> numlig;
		for(int x = 1; x <= numlig; x++)
		{
			cin >> to >> delay;
			vet[i][to] = delay;
			
			//printf("delay de %d - %d = %d\n", i, to, vet[i][to]);
		}
	}
	
	cin >> from >> to;
	
	list<int> l;
	
	l.push_back(from);
	
	dist[from] = 0;
	
	int atual;
	
	//printf("lsize: %d\n", l.size());
	while(l.size() != 0)
	{
		atual = l.front();
		l.pop_front();
		
		//printf("lsize: %d analisando: %d\n", l.size(), atual);
		
		//exit(0);
		
		for(int i = 1; i <= 10; i++)
		{
			// tiver setado um delay
			if(vet[atual][i] != 50001)
			{
				//printf("vet[%d][%d] = %d\n", atual, i, vet[atual][i]);
				// se ele ainda n tiver sido percorrido
				// adicionar ele na lista
				if(path[i] == -1 && i != to)
				{
					l.push_back(i);
				}
				
				int distancia = vet[atual][i] + dist[atual];
				
				// se o delay ja setado for maior que o atual
				if(dist[i] > distancia)
				{
					dist[i] = distancia;
					path[i] = atual;
					
					//printf("dist[%d] = %d\n", i, dist[i]);
				}
			}
		}
	}	
	
	cout << "Case " << cases << ": Path =";
	atual = to;
	list<int> caminho;
	
	do
	{
		caminho.push_front(atual);
		atual = path[atual];
	} while(atual != -1);

	if(caminho.size() == 1)
	{
		caminho.push_front(caminho.front());
	}
	
	list<int>::iterator k = caminho.begin();
	for(; k != caminho.end(); k++)
	{
		cout << " " << *k;
	}
	
	cout << "; " << dist[to] << " second delay" << endl;
	cases++;
	goto inicio;
	
	return 0;
}

Code: Select all

package volume_iii;

import java.util.Scanner;

public class P341_3747 {
    public static void main(String[] args) {
        new P341_3747().begin();
    }

    private long[][] graph;
    private int[][] intermediate;
    private int v;
    private static final long INFINITE = 67108864;

    private void begin() {
        Scanner scn = new Scanner(System.in);
        v = scn.nextInt();
        int tc = 1;
        while (v != 0 ) {
            //Lê o grafo
            initGraph(v);

            for ( int i = 1; i <= v; i++ ) {
                int e = scn.nextInt();
                for ( int j = 0; j < e; j++ ) {
                    int w = scn.nextInt();
                    int peso = scn.nextInt();
                    graph[i][w] = peso;
                }
            }

            floydWarshall();

            int from = scn.nextInt();
            int to = scn.nextInt();

            System.out.println("Case " + (tc++) + ": Path = " + getPath(from,to) + "; " + graph[from][to] + " second delay");

            v = scn.nextInt();
        }
    }

    private String getPath(int from, int to) {
        int e = intermediate[from][to];
        if ( e == 0 ) {
            return from + " " + to;
        } else {
            return getPath(from, e) + getPath(e, to).substring(1);
        }
    }

    private void floydWarshall() {
        intermediate = new int[v+1][v+1];
        for ( int k = 1; k <= v; k++ ) {
            for ( int i = 1; i <= v; i++ ) {
                for ( int j = 1; j <= v; j++ ) {
                    if ( graph[i][k]+graph[k][j] < graph[i][j] ) {
                        graph[i][j] = graph[i][k]+graph[k][j];
                        intermediate[i][j] = k;
                    }
                }
            }
        }
    }

    private void initGraph(int v) {
        graph = new long[v+1][v+1];
        for ( int i = 1; i <= v; i++ ) {
            for ( int j = 1; j <= v; j++ ) {
                if ( i != j ) {
                    graph[i][j] = INFINITE;
                }
            }
        }
    }
}

Code: Select all

#include<stdio.h>
#define INF 2147483647

long i[15][15],d,path[15];

void inter(long a, long b){
 if(i[a][b]!=0){
   inter(a,i[a][b]);
   inter(i[a][b],b);
   path[++d]= i[a][b];
   }
}

int main(){

long c[15][15],j,k,l,n,m,p,q,kase=0;

while(scanf("%ld",&n)&&n){
       d=0;

      for(l=1;l<=n;++l){
        for(k=1;k<=n;++k){
          c[l][k]=INF;
          i[l][k]=0;
         }
       }

      for(l=1;l<=14;++l)
        path[l]=0;

      for(j=1;j<=n;++j){
        scanf("%ld",&m);
       for(l=1;l<=m;++l){
         scanf("%ld%ld",&p,&q);
         c[j][p]=q;
        }
      }

scanf("%ld%ld",&p,&q);

for(k=1;k<=n;++k){
 for(l=1;l<=n;++l){
   for(j=1;j<=n;++j){
    if(c[l][k]!=INF && c[k][j]!=INF && l!=j){
     if( c[l][j] > ( c[l][k]+c[k][j] )){
         c[l][j] = c[l][k]+c[k][j];
         i[l][j]=k;
     }
    }
   }
  }
 }


inter(p,q);

printf("Case %ld: Path = %ld ",++kase,p);

  for(l=1;l<=d;++l)
    printf("%ld ",path[l]);

printf("%ld; %ld second delay\n",q,c[p][q]);


}
 return 0;
}

Code: Select all

5
2  3 3   4 6
3  1 2   3 7   5 6
1  4 5
0
1  4 7
2 2

2
1   2 5
1   1 6
1 2

7
4   2 5   3 13   4 8   5 18
2   3 7   6 14
1   6 6
2   3 5   5 9
3   6 2   7 9    4 6
1   7 2
0
1 7

0

Code: Select all

Case 1: Path = 2 2; 0 second delay
Case 2: Path = 1 2; 5 second delay
Case 3: Path = 1 2 3 6 7; 20 second delay