OJ Board

Code: Select all

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
const int infinity = 1000000000;

struct data {
    long city,H, dist;
    bool operator < ( const data& p ) const {
        return dist > p.dist;
    }
};

int main()
{
   long I,K,L,M,N,NoCity,NoHtl,NoRut;
   
   while(scanf("%ld",&NoCity)&&NoCity>0)
   {
      scanf("%ld",&NoHtl);
      bool Hotel[100003]={0};
      while(NoHtl--)
      {
         scanf("%ld",&K);
         Hotel[K]=1;
      }
      
      vector<long> Edge[10009],Cost[10009];
      scanf("%ld",&NoRut);
      while(NoRut--)
      {
         scanf("%d %d %d",&I,&K,&L);
         Edge[I].push_back(K);
         Edge[K].push_back(I);
         Cost[I].push_back(L);
         Cost[K].push_back(L);
      }
      
      bool Status[10009]={0};
      N=infinity;
      priority_queue<data>Q;
      data u,v;
      
      u.city=1;
      u.dist=0;
      u.H=0;
      
      Q.push(u);
      while(!Q.empty())
      {
         u=Q.top();
         Q.pop();
         if(u.city==NoCity&&N>u.H) {N=u.H;continue;}
         for(I=0;I<Edge[u.city].size();I++)
         {
            v.city=Edge[u.city][I];
            v.dist=u.dist+Cost[u.city][I];
            v.H=u.H;
            if(v.dist>600)
            {
               if(Status[v.city]==0&&Hotel[u.city]==1)
               {
                  ++v.H;
                  Q.push(v);
                  Status[v.city]=1;
               }
            }
            else if(Status[v.city]==0)
            Status[v.city]=1,Q.push(v);
            
         }
      }
      if(N==infinity) printf("-1\n");
      else printf("%d\n",N);
   }
   
   return 0;
}

Code: Select all

4
1 2
3
1 2 300
2 3 300
3 4 300
0

Code: Select all

#include <iostream>
#include <map>
#include <vector>
#include <cstdio>
#include <queue>
#include <memory.h>
using namespace std;

#define MAX 10001
typedef struct Edge
{
	int i,v;
	Edge *next;
	Edge(int ii=0,int vv=0,Edge * nnext=NULL):i(ii),v(vv),next(nnext){}
};

vector<int> hotNum;
Edge g[MAX];
Edge sG[105];
int dis[MAX];
bool vis[MAX];
bool svis[105];
int sdis[105];
int n,m,q;

int bfs(int start,int end){
	memset(sdis,0,sizeof(sdis));
	memset(svis,0,sizeof(svis));
	queue<int> q;
	q.push(start);
	vis[start]=1;
	while (q.size())
	{
		int t=q.front();
		q.pop();
		if(t==end)return sdis[t]-1;
		Edge * n=sG[t].next;
		for (;n;n=n->next)
		{
			if(!vis[n->i]){
				sdis[n->i]=sdis[t]+1;
				vis[n->i]=1;
				q.push(n->i);
			}
		}
	}
	return -1; 
}
void addEdge(Edge g[MAX],int u,int v,int w){
	Edge *n=&g[u];
	while (n->next)
	{
		n=n->next;
	}
	n->next=new Edge(v,w);
	n->next->next=NULL;
}
void spfa(int start,int index){
	memset(dis,0X7F,sizeof(int)*(n+1));
	memset(vis,0,sizeof(bool)*(n+1));
	dis[start]=0;
	queue<int>q;
	q.push(start);
	vis[start]=1;
	while (q.size())
	{
		int t=q.front();
		q.pop();
		vis[t]=0;
		Edge *n=g[t].next;
		for (;n;n=n->next)
		{
			if(dis[n->i]>dis[t]+n->v){
				dis[n->i]=dis[t]+n->v;
				if(!vis[n->i]){
					vis[n->i]=1;
					q.push(n->i);
				}
			}
		}
	}
	for (int i=0;i<hotNum.size();++i)
	{
		if(i==index)continue;
		if(dis[hotNum[i]]<=600){
			addEdge(sG,index,i,1);
		}
	}
}


int main(){
	while (cin>>n,n)
	{
		int i;
		cin>>q;
		hotNum.clear();
		memset(g,0,sizeof(g[0])*(n+1));
		memset(sG,0,sizeof(sG));
		hotNum.push_back(1);
		hotNum.push_back(n);
		for (i=0;i<q;++i)
		{
			int t;
			scanf("%d",&t);
			if(t!=1&&t!=n)
			hotNum.push_back(t);
		}
		cin>>m; 
		for (i=0;i<m;++i)
		{
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			addEdge(g,u,v,w);
			addEdge(g,v,u,w);
		}
		for (i=0;i<hotNum.size();++i)
		{
			spfa(hotNum[i],i);
		}
		cout<<bfs(0,1)<<endl;
	}
	return 0;
}

Code: Select all

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
class Town {
public:
   bool hotel;
   int min;
   int day;
   vector<pair<int,int> > adj;
   Town() {
      hotel=false;
	  min=0x3f3f3f3f;
	  day=0x3f3f3f3f;
	  adj.clear();
   }
};
class Comp {
public:
	bool operator () (Town* ptr1, Town* ptr2) {
		if(ptr1->day!=ptr2->day) return (ptr1->day > ptr2->day);
		if(ptr1->min!=ptr2->min) return (ptr1->min > ptr2->min);
		return false;
	}
};
Town map[20001];
const int debug =0;
int main() {
	int num_of_town;
	while(cin >> num_of_town && num_of_town!=0){
	 for(int i=1;i<=num_of_town;i++)map[i]=Town();
	 for(int i=1;i<=num_of_town;i++)map[i+10000]=Town();
		int num_of_hotel;
	 cin >> num_of_hotel;
	 for(int i=0;i<num_of_hotel;i++){
		 int t;
		 cin >>t;
		 map[t].hotel=true;
	 }
	 int num_of_road;
	 cin >> num_of_road;
	 for(int i=0;i<num_of_road;i++) {
	    int t1, t2, length;
		cin >> t1 >> t2 >> length;
		map[t1].adj.push_back(make_pair<int,int>(t2,length));
		map[t2].adj.push_back(make_pair<int,int>(t1,length));
		if(map[t1].hotel) {
			map[t2].adj.push_back(make_pair<int,int>(t1+10000,length));
			map[t1+10000].adj.push_back(make_pair<int,int>(t2,length));
		}
		if(map[t2].hotel) {
			map[t1].adj.push_back(make_pair<int,int>(t2+10000,length));
			map[t2+10000].adj.push_back(make_pair<int,int>(t1,length));			 
		}
	 }
	 priority_queue<Town*,vector<Town*>,Comp> qu;
	 qu=priority_queue<Town*,vector<Town*>,Comp>();
	 map[1].day=map[1].min=0;
	 qu.push(&map[1]);
	 while(!qu.empty() && qu.top()!=&map[num_of_town] ) {
	   Town* tptr=qu.top();
	   
	   vector<pair<int,int> >&a=tptr->adj;
	   vector<pair<int,int> >::iterator it = a.begin();
	   for(;it!=a.end();it++) {
		   int dst=it->first;
		   int time=it->second;
		   if((tptr->min+time)<=600 ){
			   if(map[dst].hotel && (tptr->day < map[dst].day-1)){
				   map[dst].day=tptr->day+1;
				   map[dst].min=0;
				   qu.push(&map[dst]);
			   } else if (!map[dst].hotel &&  (tptr->day!=map[dst].day || (tptr->day==map[dst].day &&
				    tptr->min+time < map[dst].min) )) {
				   map[dst].day=tptr->day;
				   map[dst].min=tptr->min + time;
				   qu.push(&map[dst]);
			   } 
		   }
	   }
	   qu.pop();
	 }
	 if(!qu.empty()) {
	 cout << map[num_of_town].day << endl;
	 } else {
	  cout << -1 <<endl;
	 }
	}
return 0;
}

Code: Select all

2
1 2
1
1 2 1
0

Code: Select all

0

Code: Select all

#include <iostream>
#include <map>
#include <vector>
#include <limits.h>
#include <stdio.h>

using namespace std;

struct _NODE;

typedef struct
{
    int driveDistance;              // distance I am driving since last slept
    int distLastHotel;              // distance to last passed hotel, where I did not sleep
    int cHotelsSlept;               // number of hotels I slept in
} DIST, *PDIST;

typedef pair<_NODE *, int> EDGE, *PEDGE;

typedef struct _NODE
{
    int predecessor;            // the node before
    bool visited;               // visited during dijkstra algorithm
    int id;                     // the id of the node
    bool isHotel;               // is it a hotel?
    DIST distance;              // distance to source node
    vector<EDGE> edges;         // my edges
} NODE, *PNODE;

typedef bool (*PFNCOMP)(const DIST&, const DIST&);
typedef multimap<DIST, PNODE, PFNCOMP> NODEMAP, *PNODEMAP;


int g_MAXDISTANCE = 600;
int g_BIGHOTELDISTANCE = 1000;

bool distLess( const DIST &distLeft, const DIST &distRight)
{
    int diff = distLeft.cHotelsSlept - distRight.cHotelsSlept;
    bool less = (diff < 0 ? true :
                 ( diff > 0 ? false :
                   ( distLeft.driveDistance < distRight.driveDistance)));
    return less;
}

void calcDist( NODE &nodeSrc, EDGE &edge, PDIST pDist )
{
    PNODE pNodeDest = edge.first;

    // check if I can reach the destination
    int oldDistance = nodeSrc.distance.driveDistance;
    int driveDistance = (oldDistance == INT_MAX) ? INT_MAX : oldDistance + edge.second;

    // distance too large?
    if( driveDistance > ::g_MAXDISTANCE ) {
        // try to sleep in formely visited hotel
        if( (nodeSrc.distance.distLastHotel != INT_MAX) && (nodeSrc.distance.distLastHotel + edge.second <= ::g_MAXDISTANCE) ) {
            pDist->cHotelsSlept = nodeSrc.distance.cHotelsSlept + 1;
            pDist->driveDistance = nodeSrc.distance.distLastHotel + edge.second;
            pDist->distLastHotel = pNodeDest->isHotel ? 0 : INT_MAX;
        }
        // cannot sleep => node not reachable
        else {
            pDist->cHotelsSlept = g_BIGHOTELDISTANCE;
            pDist->driveDistance = INT_MAX;
            pDist->distLastHotel = INT_MAX;
        }
    }
    // distance ok, and dest node is a hotel.
    else if( pNodeDest->isHotel) {
        pDist->cHotelsSlept = nodeSrc.distance.cHotelsSlept;
        pDist->distLastHotel = 0;
        pDist->driveDistance = nodeSrc.distance.driveDistance+edge.second;
    }
    // distance ok and no hotel
    else {
        pDist->cHotelsSlept = nodeSrc.distance.cHotelsSlept;
        pDist->distLastHotel = (nodeSrc.distance.distLastHotel == INT_MAX) ? INT_MAX : nodeSrc.distance.distLastHotel + edge.second;
        pDist->driveDistance = (nodeSrc.distance.driveDistance == INT_MAX) ? INT_MAX : nodeSrc.distance.driveDistance + edge.second;
    }
}

void updateMap( NODEMAP &nodesNotVisited, PNODE pNode, DIST &distNew, bool fInsert )
{
    NODEMAP::iterator it = nodesNotVisited.find( pNode->distance);
    while( (it->second != pNode) &&   (it != nodesNotVisited.end()) )
        it++;
    if( it != nodesNotVisited.end() )
    {
        nodesNotVisited.erase( it );
        if( fInsert )
        {
            pNode->distance.cHotelsSlept = distNew.cHotelsSlept;
            pNode->distance.driveDistance = distNew.driveDistance;
            pNode->distance.distLastHotel= distNew.distLastHotel;
            nodesNotVisited.insert( pair<DIST, PNODE>(pNode->distance, pNode) );
        }
    }
}

int solve( NODEMAP &nodesNotVisited, int idSrc, int idDest )
{
    int maxDistance = -1;
    bool fLoop = (nodesNotVisited.size() > 0);
    while( fLoop )
    {
        // get node with shortest distance
        PNODE pNodeMin = nodesNotVisited.begin()->second;

        // if its the destination node, are we finished
        if( pNodeMin->id == idDest )
        {
            maxDistance = pNodeMin->distance.cHotelsSlept;
            if( maxDistance >= g_BIGHOTELDISTANCE)
                maxDistance = -1;
            fLoop = false;
        }
        // if this node already has too big a hotel distance, then there is no solution at all
        else if( pNodeMin->distance.cHotelsSlept < g_BIGHOTELDISTANCE )
        {
            int cEdges = pNodeMin->edges.size();

            // check all edges of this node in order to get shorter paths
            for( int idxEdge = 0; idxEdge < cEdges; ++idxEdge )
            {
                PEDGE pEdge = &(pNodeMin->edges[idxEdge]);
                PNODE pNodeDest = pEdge->first;
                DIST newDist; calcDist( *pNodeMin, *pEdge, &newDist);
                if( distLess( newDist, pNodeDest->distance))
                {
                    updateMap( nodesNotVisited, pNodeDest, newDist, true);
                    pNodeDest->predecessor = pNodeMin->id;
                }
            }

            // remove node with the shortest distance from the multimap
            pNodeMin->visited = true;
            updateMap( nodesNotVisited, pNodeMin, pNodeMin->distance, false);

            // check if loop is finished
            if( nodesNotVisited.size() == 0 )
                fLoop = false;
            else if( pNodeMin->id == idDest ) {
                fLoop = false; maxDistance = pNodeMin->distance.cHotelsSlept;
            }
        }
        else {
            fLoop = false;
        }
    }

    return maxDistance;
}

int main()
{
    vector<int> solutions;

    while( true )
    {
        // get number of cities
        int cCities = 0; scanf( "%d", &cCities ); if( cCities == 0 ) break;

        // allocate an array and fill it with the nodes
        PNODE aNodes = new NODE[cCities];
        for( int idx = 0; idx < cCities; ++idx )
        {
            aNodes[idx].distance.cHotelsSlept = aNodes[idx].distance.driveDistance =
            ( idx == 0 ? 0 : INT_MAX);
            aNodes[idx].distance.distLastHotel = INT_MAX;
            aNodes[idx].id = idx+1;
            aNodes[idx].predecessor = 0;
            aNodes[idx].isHotel = false;
            aNodes[idx].visited = false;
        }

        // get hotels
        int cHotels = 0; scanf( "%d", &cHotels);
        for( int idxH = 0; idxH < cHotels; ++idxH)
        {
            int h = 0;
            if( idxH+1 < cHotels )
                scanf( "%d", &h);
            else
                scanf( "%d", &h);
            aNodes[h-1].isHotel = true;
        }

        // get edges
        int cEdges = 0; scanf( "%d", &cEdges);
        for( int idxE = 0; idxE < cEdges; ++idxE)
        {
            int nodeSrc = -1, nodeDest = -1, dist = -1;
            scanf("%d %d %d", &nodeSrc, &nodeDest, &dist);
            PNODE pNodeSrc = &(aNodes[nodeSrc-1]), pNodeDest = &(aNodes[nodeDest-1]);
            pNodeSrc->edges.push_back(EDGE( pNodeDest, dist ));
            pNodeDest->edges.push_back(EDGE( pNodeSrc, dist ));
        }

        // construct the nodemap
        NODEMAP nodesNotVisited( distLess );
        for( int idx = 0; idx < cCities; ++idx)
        {
            PNODE pNode = &(aNodes[idx]);
            nodesNotVisited.insert( pair<DIST, PNODE>(pNode->distance,pNode));
        }

        // solve the test case
        int solution = solve( nodesNotVisited, 1, cCities);
        solutions.push_back( solution );
    }

    int cSolutions = solutions.size();
    for(int idx = 0; idx < cSolutions; idx++)
    {
        printf( "%d\n", solutions[idx] );
    }
}

Code: Select all

9
6 4 8 2 3 6 5
8
1 6 476
7 5 49
2 9 488
5 4 151
5 8 537
2 7 367
1 6 509
6 7 430

6
4 2 4 1 6
11
5 2 328
6 3 249
3 5 150
5 4 501
5 1 220
3 5 520
4 1 378
3 2 116
4 1 476
1 3 418
4 2 562

9
4 5 2 6 7
16
3 5 280
7 5 419
2 8 226
7 1 135
3 9 413
8 3 293
4 1 76
5 3 490
7 5 16
1 7 271
3 8 148
1 5 438
6 4 237
8 1 129
5 3 217
3 2 165

0

Code: Select all

3
1
1

Code: Select all

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct edge
{
     int d,t;
     edge(int din,int tin): d(din), t(tin){};
};

struct node
{
     bool hotel,hv;
     int t,v;
     vector<edge> links;
     node(): hotel(false), hv(false),t(1000),v(0){links.clear();}
};

node towns[10001];
queue<int> hoteltv;
int turn=0;

bool bfs(int start, int goal)
{
     queue<int> visit;
     visit.push(start);
     towns[start].v = turn;
     towns[start].t = 0;
     while(!visit.empty()){
	  int current = visit.front();	  
	  visit.pop();
	  if (current == goal){
	       return true;
	  }
	  node& city = towns[current];
	  if (!city.hv && city.hotel){;
	       hoteltv.push(current);
	       city.hv=1;
	  }
	  for (edge link : city.links){
	       int next = link.d;
	       int tv = link.t + city.t;
	       if (tv <= 600 && (towns[next].v != turn || tv < towns[next].t))
	       {
		    towns[next].v = turn;
		    towns[next].t = tv;
		    visit.push(next);
	       }	       
	  }
     }     
     return false;
}

int solve(int goal)
{
     if(bfs(1,goal))
	  return turn;
     while(!hoteltv.empty()){
	  turn++;
	  int n = hoteltv.size();
	  for (int i = 0; i < n; i++){
	       int start = hoteltv.front();
	       hoteltv.pop();
	       if(bfs(start,goal))
		    return turn;	       
	  }	  
     }
     return -1;
}

int main()
{
     int n, h, a, b,t, m;
     while(cin>>n && n!=0){
	  cin >> h;
	  for (int i = 0; i <= n; i++){
	       towns[i] = node();
	  }
	  for (int i = 0; i <h; i++){
	       cin >> a;
	       towns[a].hotel = true;
	  }
	  cin >> m;
	  for (int i = 0; i < m; i++){
	       cin >> a >> b >> t;
	       towns[a].links.push_back(edge(b,t));
	       towns[b].links.push_back(edge(a,t));
	  }
	  int hn = solve(n);     
	  hn >= 0 ? cout << hn : cout << -1;
	  cout << endl;
	  turn = 0;
     }
     return 0;
}