UVA 11280 - Flying to Fredericton SPFA变形

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2255&mosmsg=Submission+received+with+ID+13067799

题目大意：

给出n（2<=n<=100)个城市之间的m（0<=m<=1000）条航线以及对应的机票价格，要求回答一些询问，每个询问是给出最大停留次数S，求从其实城市Calgary到终点城市Fredericton中途停留次数不超过s的最便宜的路程。

思路：

这题坑爹的是用城市名，不是直接编号了，嗯，map搞定之。

SPFA的变形，用二维数组dis[i][j]记录到顶点i步数为j的最短路径。

最后根据要求的s遍历一下即可~

坑爹的是s可能大于顶点数，然后我初始化坑了一回QAQ

#include<cstdio>

#include<cstring>

#include<string>

#include<map>

#include<queue>

#include<algorithm>

#include<iostream>

using namespace std;

const int MAXN=100+10;

const int MAXM=1000+10;

const int INF=99999999;

int head[MAXN],len,n,m,dis[MAXN][MAXN],vis[MAXN][MAXN];

struct edge

{

	int to,val,next;

}e[MAXM];

void add(int from,int to,int val)

{

	e[len].to=to;

	e[len].val=val;

	e[len].next=head[from];

	head[from]=len++;

}

struct node

{

	int id,cnt;

	node(int x,int c){cnt=c; id=x;}

};

void spfa(int s,int target,int tol)

{

	memset(vis,0,sizeof(vis));

	for(int i=0;i<=n+1;i++)			//n+1坑啊，WA到爆，检查一个多小时才发现！！！

		for(int j=0;j<=n+1;j++)

			dis[i][j]=INF;

	queue<node> q;

	q.push(node(s,0));

	vis[s][0]=true;

	dis[s][0]=0;

	while(!q.empty())

	{

		node cur=q.front();

		q.pop();

		vis[cur.id][cur.cnt]=false;

		for(int i=head[cur.id];i!=-1;i=e[i].next)

		{

			int id=e[i].to;

			if(e[i].val + dis[cur.id][cur.cnt] < dis[id][cur.cnt+1])

			{

				dis[id][cur.cnt+1] = e[i].val + dis[cur.id][cur.cnt] ;

				if(!vis[id][cur.cnt+1])

				{

					vis[id][cur.cnt+1]=true;

					q.push(node(id,cur.cnt+1));

				}

			}

		}

	}

}

int main()

{

	int T;

	scanf("%d",&T);

	for(int ri=1;ri<=T;ri++)

	{

		memset(head,-1,sizeof(head));

		len=0;

		map<string,int> name;

		scanf("%d",&n);

		string a,b;

		for(int i=1;i<=n;i++)

		{

			cin>>a;

			name[a]=i;

		}

		int cost;

		scanf("%d",&m);

		for(int i=0;i<m;i++)

		{

			cin>>a>>b>>cost;

			add(name[a],name[b],cost);

		}

		int start=name["Calgary"],fin=name["Fredericton"];

		int k,tolerate;

		scanf("%d",&k);

		if(ri!=1)

			printf("\n");

		spfa(start,fin,n+1);

		printf("Scenario #%d\n",ri);

		for(int i=0;i<k;i++)

		{

			scanf("%d",&tolerate);

			tolerate= min(tolerate, n); //坑啊

			int ans=INF;

			for(int j=0;j<=tolerate+1;j++)

				ans=min(dis[fin][j],ans);

			if(ans!=INF)

				printf("Total cost of flight(s) is $%d\n", ans);

			else

				printf("No satisfactory flights\n");

		}

	}

	return 0;

}

巴特西

UVA 11280 - Flying to Fredericton SPFA变形

最新文章

热门文章