Блог пользователя kavishrox

Автор kavishrox, 11 лет назад, По-английски

I wrote the following code using dijkstra's for the problem but can't determine why the answer is going wrong . [](http://www.spoj.com/problems/FPOLICE/) http://www.spoj.com/problems/FPOLICE/

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<utility>
#include<climits>
using namespace std;
#define mp make_pair
main()
{
	int n,tc,t;
	scanf("%d",&tc);
	while(tc--)
	{
		scanf("%d%d",&n,&t);
		vector<vector<int> > dist,risk;
		dist.resize(n);
		risk.resize(n);
		for(int i=0;i<n;i++)
		{
			dist[i].resize(n);
			for(int j=0;j<n;j++)
				scanf("%d",&dist[i][j]);
		}
		for(int i=0;i<n;i++)
		{
			risk[i].resize(n);
			for(int j=0;j<n;j++)
				scanf("%d",&risk[i][j]);
		}
		queue <pair<int,int> > q;
		vector <vector<int> > dp;
		vector <vector<bool> > ch;
		dp.resize(t+1);
		ch.resize(t+1);
		for(int i=0;i<t+1;i++)
		{
			ch[i].resize(n,false);
			dp[i].resize(n,INT_MAX);
		}
/*-----------------------------------------------------------------------------------------------------*/
		//DIJKSTRA'S starts here 
		dp[0][0]=0;
		q.push(mp(0,0));
		ch[0][0]=true;
		while(q.size())
		{
			pair<int,int> myp=q.front();
			//cout<<myp.first<<" "<<myp.second<<endl;
			q.pop();
			ch[myp.first][myp.second]=false;
			int amt=dp[myp.first][myp.second];
			for(int i=0;i<n;i++)
			{
				//cout<<"Hi2"<<endl;
				if(i!=myp.second)
				{
					//cout<<"Hi3"<<endl;
					int nt=dist[myp.second][i]+myp.first;
					if(nt>t)
						continue;
					int tot=amt+risk[myp.second][i];
					if(tot<dp[nt][i])
					{
						//cout<<"Hi"<<endl;
						dp[nt][i]=tot;
						if(!ch[nt][i])
						{
							//cout<<"Hi1"<<endl;
							ch[nt][i]=true;
							q.push(mp(nt,i));
						}
					}
				
				}
			}
		}
		int min=INT_MAX,x;
		for(int i=0;i<=t;i++)
			if(dp[i][n-1]<min)
			{
				min=dp[i][n-1];
				x=i;
			}
		printf("%d %d\n",min,x);
	}
	return 0;
}

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

EDIT: Corrected . It was a silly one .