Til the Cows Come Home

Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 92816 Accepted: 30207

Description

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.

Farmer John’s field has N (2 <= N <= 1000) landmarks in it, uniquely numbered 1…N. Landmark 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N. Cows travel in the field using T (1 <= T <= 2000) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.

Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.
Input

  • Line 1: Two integers: T and N

  • Lines 2…T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1…100.
    Output

  • Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.
    Sample Input

5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output

90
Hint

INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.

题目大意:有个人在田里面放羊然后他想回去睡觉,然后回去需要经过几个点,题目给出每个点的距离,要你求从1到n距离最短是多少?
思路:最短路裸题,一开始floyd写的超时了,也是哈明明是单源我却偏偏要多源wa一次,改dijkstra ac了
会prime就会dijkstra额感觉就一点点不同,都是贪心思想过来的。
代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e3+10;
const int inf=0x3f3f3f3f;
int t,n;
int vis[maxn];
int dis[maxn];
int a[maxn][maxn];
void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	memset(dis,88,sizeof(dis));
	dis[s]=0;vis[s]=1;
	for(int i=1;i<=n;i++){
		dis[i]=min(dis[i],a[s][i]);
	}
	for(int p=1;p<=n-1;p++){
		int minn=inf,k;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis[i]<minn){
				minn=dis[i];
				k=i;
			}
		}
		vis[k]=1;
		for(int i=1;i<=n;i++){
			dis[i]=min(dis[i],dis[k]+a[k][i]);
		}
	}
	cout<<dis[n]<<endl;
}
int main(){
	memset(a,88,sizeof(a));
	cin>>t>>n;
	int x,y,z;
	for(int i=1;i<=t;i++){
		cin>>x>>y>>z;
		if(z<a[x][y])a[x][y]=a[y][x]=z;
	}
	dijkstra(1);
}

Heavy Transportation

Time Limit: 3000MS Memory Limit: 30000K Total Submissions: 60820 Accepted: 15138

Description

Background
Hugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.
Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea how to find the the maximum weight capacity in order to tell his customer how heavy the crane may become. But you surely know.

Problem
You are given the plan of the city, described by the streets (with weight limits) between the crossings, which are numbered from 1 to n. Your task is to find the maximum weight that can be transported from crossing 1 (Hugo’s place) to crossing n (the customer’s place). You may assume that there is at least one path. All streets can be travelled in both directions.
Input

The first line contains the number of scenarios (city plans). For each city the number n of street crossings (1 <= n <= 1000) and number m of streets are given on the first line. The following m lines contain triples of integers specifying start and end crossing of the street and the maximum allowed weight, which is positive and not larger than 1000000. There will be at most one street between each pair of crossings.
Output

The output for every scenario begins with a line containing “Scenario #i:”, where i is the number of the scenario starting at 1. Then print a single line containing the maximum allowed weight that Hugo can transport to the customer. Terminate the output for the scenario with a blank line.
Sample Input

1
3 3
1 2 3
1 3 4
2 3 5
Sample Output

Scenario #1:
4

最长路选最小值,稍微调整一下dijkstra就行了。
代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;

int dis[1010];
int vis[1010];
int a[1010][1010];
int n,m;
void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	vis[s]=1;
	for(int i=1;i<=n;i++){
		dis[i]=a[s][i];
	}
	dis[1]=0;
	for(int q=1;q<=n-1;q++){
		int minn=0,k;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis[i]>minn){
				minn=dis[i];
				k=i;
			}
		}
		vis[k]=1;
		for(int i=1;i<=n;i++){//最长路选最小值 
			if(!vis[i]&&dis[i]<a[k][i])
			dis[i]=min(dis[k],a[k][i]); 
		}
	}
	cout<<dis[n]<<endl<<endl;//这里是两个换行 
}
int main(){
	int plan;
	cin>>plan;
	for(int q=1;q<=plan;q++){
		memset(a,0,sizeof(a));
		cin>>n>>m;
		int x,y,z;
		for(int i=1;i<=m;i++){
			cin>>x>>y>>z;
			a[x][y]=a[y][x]=z;
		}
		cout<<"Scenario #"<<q<<":"<<endl;
		dijkstra(1);
	}
}

Silver Cow Party
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 35754 Accepted: 16004

Description

One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1…N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.

Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow’s return route might be different from her original route to the party since roads are one-way.

Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?

Input

Line 1: Three space-separated integers, respectively: N, M, and X
Lines 2…M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output

Line 1: One integer: the maximum of time any one cow must walk.
Sample Input

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
Sample Output

10
Hint

Cow 4 proceeds directly to the party (3 units) and returns via farms 1 and 3 (7 units), for a total of 10 time units.

这个题感觉还不错,我前面wa了好多次。。。。原来是英文没看懂我以为求n到x和x到n的最小值之和,然后看了讨论才知道是求每头牛要来回的最短时间中的最大值。。。不知道说清楚没有。。。。。(应该说清楚了)。
思路:用dijkstra跑两次,第一次是终点到各点最短距离存到一个数组。(来
第二次各个点距离到终点距离最短距离存到一个数组。(回
然后求最大值就可以了。
代码:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+10;
const int inf=0x7fffff;

int a[maxn][maxn];
int n,m,x,q;
int vis[maxn];
int dis1[maxn];
int dis2[maxn];

void dijkstra1(){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	dis1[i]=a[q][i];
	dis1[q]=0;vis[q]=1;
	for(int p=1;p<=n-1;p++){
		int minn=inf,k;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis1[i]<minn){
				minn=dis1[i];
				k=i;
			}
		}
		vis[k]=1;
		for(int i=1;i<=n;i++){
		// if(!vis[i]&&dis1[i]<dis1[k]+a[k][i])
			dis1[i]=min(dis1[i],dis1[k]+a[k][i]);//这里比较好理解和普通dijkstra一样
		}
	}
}
void dijkstra2(){
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	dis2[i]=a[i][q];
	/*for(int i=1;i<=n;i++) cout<<dis2[i]<<" ";*/
	dis2[q]=0;vis[q]=1;
	for(int p=1;p<=n-1;p++){
		int minn=inf,k;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis2[i]<minn){
				minn=dis2[i];
				k=i;
			}
		}
		vis[k]=1;
		for(int i=1;i<=n;i++){
		// if(!vis[i]&&dis2[i]>dis2[k]+a[k][i])
			dis2[i]=min(dis2[i],dis2[k]+a[i][k]);//这里要理解一下,这里是i点x点最短距离,往前面推,不明白可以根据样例画图模拟一下
		}
	}
}
int main(){
		int x,y,z;
		cin>>n>>m>>q;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j)a[i][j]=0;
				else 
				a[i][j]=inf;
			}
		}
		for(int i=1;i<=m;i++){
			cin>>x>>y>>z;
			if(z<a[x][y])a[x][y]=z;
		} 
		dijkstra1();
		dijkstra2();
		int maxnn=dis1[1]+dis2[1];
		for(int i=2;i<=n;i++){
			if(dis1[i]+dis2[i]>maxnn){
				maxnn=dis1[i]+dis2[i];
			}
		}
		cout<<maxnn<<endl;
}

Currency Exchange

Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 42520 Accepted: 16357

Description

Several currency exchange points are working in our city. Let us suppose that each point specializes in two particular currencies and performs exchange operations only with these currencies. There can be several points specializing in the same pair of currencies. Each point has its own exchange rates, exchange rate of A to B is the quantity of B you get for 1A. Also each exchange point has some commission, the sum you have to pay for your exchange operation. Commission is always collected in source currency.
For example, if you want to exchange 100 US Dollars into Russian Rubles at the exchange point, where the exchange rate is 29.75, and the commission is 0.39 you will get (100 - 0.39) * 29.75 = 2963.3975RUR.
You surely know that there are N different currencies you can deal with in our city. Let us assign unique integer number from 1 to N to each currency. Then each exchange point can be described with 6 numbers: integer A and B - numbers of currencies it exchanges, and real RAB, CAB, RBA and CBA - exchange rates and commissions when exchanging A to B and B to A respectively.
Nick has some money in currency S and wonders if he can somehow, after some exchange operations, increase his capital. Of course, he wants to have his money in currency S in the end. Help him to answer this difficult question. Nick must always have non-negative sum of money while making his operations.
Input

The first line of the input contains four numbers: N - the number of currencies, M - the number of exchange points, S - the number of currency Nick has and V - the quantity of currency units he has. The following M lines contain 6 numbers each - the description of the corresponding exchange point - in specified above order. Numbers are separated by one or more spaces. 1<=S<=N<=100, 1<=M<=100, V is real number, 0<=V<=103.
For each point exchange rates and commissions are real, given with at most two digits after the decimal point, 10-2<=rate<=102, 0<=commission<=102.
Let us call some sequence of the exchange operations simple if no exchange point is used more than once in this sequence. You may assume that ratio of the numeric values of the sums at the end and at the beginning of any simple sequence of the exchange operations will be less than 104.
Output

If Nick can increase his wealth, output YES, in other case output NO to the output file.
Sample Input

3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00
Sample Output

YES

题目大意:(这个翻译好难。。。,翻译了无数遍)
一些货币交易点在我市运营,我们假设每个交易点专门从事两种货币运营,每个运营点有自己的交易汇率和佣金,也就是说你要将100美元换成俄罗斯卢布的话,假设这家交易所的汇率是29.75,佣金是0.39,那么你兑换的俄罗斯卢布是(100-0.39)*29.75=2963.3975rur,你肯定知道在你的城市有n中货币,假设货币用阿拉伯数字1到N表示,每个交易所可以用6个数字描述,A B RAB CAB RBA CBA,分别代表将货币A兑换成B,RAB:A兑换成B的汇率,CAB:A兑换成B的佣金,RBA:B兑换成A的汇率,CBA:B兑换成A的佣金,然后NICK有一种货币S,然后这种货币他有的资产是V,问你能不能通过不断去交易所兑换钱后,最后在换成货币S,他还能不能赚钱?大概就算这么个意思。
简单说一下样例,看了半天才看懂(菜的我。。。),有3种货币,两个交易所,然后NICK拥有的货币种类是1,资产是20.0,然后NICK可以先去第一个交易所将货币1换成货币2,资产=(20.0-1.0)*1.0=19.0,然后将货币2去换成货币2(在第二个交易所换),资产=(19.0-1.0)*1.1=19.8,然后将货币3换成货币2,资产=(19.8-1.0)*1.1=20.68,再将货币2换成货币3,资产=(20.68-1.0)*1.1=21.648,然后通过这样不断换,最后再去第一个交易所换回来原来的货币S,这样肯定是可以赚的,所以输出YES。
思路:bellman-ford,网上看的代码,临时学习了一个bellman-ford,代码比较简单几句话就搞定了,理解还是需要花一点时间的,bellman-ford主要是通过不断松弛+迭代实现的。
针对这题,我们可以想想一下,将n种货币,想象成图论的顶点,而交易所则是连接两个相同顶点两条边,权值分别是汇率和佣金,这题的突破口就是需要找一个正环,能让NICK不断将钱换来换去达到赚钱的一个目的,所以用bellman-ford来找这个正环就可以了,因为今天第一次学习bellman-ford存在一些理解问题,就不对代码进行解释了。
代码:


//bellman-ford

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

int n,m,s;
double v;

double dis[101];

typedef struct{
	int a,b;
	double c,r;
}edge;
edge edges[202];
int cnt;
bool bellman_ford(){
	memset(dis,0,sizeof(dis));//求最大环 
	dis[s]=v;
	for(int k=1;k<=n-1;k++){
		for(int i=0;i<cnt;i++){
			if(dis[edges[i].b]<(dis[edges[i].a]-edges[i].c)*edges[i].r){
				dis[edges[i].b]=(dis[edges[i].a]-edges[i].c)*edges[i].r;
			}
		}
	}
	for(int i=0;i<cnt;i++){
		if(dis[edges[i].b]<(dis[edges[i].a]-edges[i].c)*edges[i].r){
			return true;
		}
	}
	return false;
}
int main(){
	
	int a,b;
	double rab,cab,rba,cba;
	while(cin>>n>>m>>s>>v){
		cnt=0;
			for(int i=1;i<=m;i++){
			cin>>a>>b>>rab>>cab>>rba>>cba;
			edges[cnt].a=a;
			edges[cnt].b=b;
			edges[cnt].r=rab;
			edges[cnt++].c=cab;
			edges[cnt].a=b;
			edges[cnt].b=a;
			edges[cnt].c=cba;
			edges[cnt++].r=rba;
		}
		if(bellman_ford()){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
}

Wormholes

Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 74795 Accepted: 27820

Description

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1…N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself ? .

To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2…M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2…M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
Output

Lines 1…F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).
Sample Input

2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output

NO
YES
Hint

For farm 1, FJ cannot travel back in time.
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

题目大意:就是有n个农场编号从1到N,然后农场与农场之间存在一些路(有单向也有双向),农场A到农场B需要花费时间T秒,某些农场里面有黑洞,这个黑洞可以让你退回T秒之前所在的位置,然后题目问你在给出的地图F中能不能不花时间回到原来的起点。
思路:题目好像并没有说起点,然后我是从1好点做起点的,结果ac了,题目问我们能不能回到起点不花时间,那么我们需要找一条连接了起点的环路,并且这个环路的权值之和是负数,这样才能不花费时间回到起点,题目在退化一下就是求负环了,然后用bellman-ford跑一下就出来了,额。。。然后今天刚学bellman-ford,才知道图论居然还可以这样玩,bellman-ford和dijkstra都是求单源最短路但是bellman-ford可以求带负权的最短路,而dijkstra就不行,然后如果一个换中权之和为负数,我们称这个环为负环,(找了好久的概念),本来下午感觉这个bellman-ford有点奇怪,然后在洛谷过了一个模板题,渐渐的也能慢慢的理解了,然后这种图论最短路的变形题也还是有一点点难理解,加油吧!!!
代码:

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

const int maxn=1e5+10;
int f,n,m,w;
typedef struct{
	int from,to,w;
}edge;
edge edges[maxn];
int dis[maxn];
int cnt;
bool bellma_ford(){//这里就很基础了
	memset(dis,88,sizeof(88));
	dis[1]=0;
	for(int i=1;i<=n-1;i++){
		for(int j=0;j<cnt;j++){
			if(dis[edges[j].to]>dis[edges[j].from]+edges[j].w){
				dis[edges[j].to]=dis[edges[j].from]+edges[j].w;
			}
		}
	} 
	for(int j=0;j<cnt;j++){//如果存在负环那么这个距离还能一直更新到为-无穷,我们不需要让他更新,看一下能不能更新,能,说明存在负环
		if(dis[edges[j].to]>dis[edges[j].from]+edges[j].w){
			return true;
		}
	}
	return false;
}
int main(){
	cin>>f;
	while(f--){
		cnt=0;
		cin>>n>>m>>w;
		int x,y,z;
		for(int i=1;i<=m;i++){//m条双向边
			cin>>x>>y>>z;
			edges[cnt].from=x;
			edges[cnt].to=y;
			edges[cnt++].w=z;
			edges[cnt].from=y;
			edges[cnt].to=x;
			edges[cnt++].w=z;
		}
		for(int i=1;i<=w;i++){//w条黑洞边,因为黑洞边可以让你退回T秒之前,所以把他的权设置为负数
			cin>>x>>y>>z;
			edges[cnt].from=x;
			edges[cnt].to=y;
			edges[cnt++].w=-z;//很关键
		}
		if(bellma_ford()){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
	}
}

MPI Maelstrom
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 14226 Accepted: 8716

Description

BIT has recently taken delivery of their new supercomputer, a 32 processor Apollo Odyssey distributed shared memory machine with a hierarchical communication subsystem. Valentine McKee’s research advisor, Jack Swigert, has asked her to benchmark the new system.
Since the Apollo is a distributed shared memory machine, memory access and communication times are not uniform,'' Valentine told Swigert.Communication is fast between processors that share the same memory subsystem, but it is slower between processors that are not on the same subsystem. Communication between the Apollo and machines in our lab is slower yet.’’

``How is Apollo’s port of the Message Passing Interface (MPI) working out?’’ Swigert asked.

Not so well,'' Valentine replied.To do a broadcast of a message from one processor to all the other n-1 processors, they just do a sequence of n-1 sends. That really serializes things and kills the performance.’’

``Is there anything you can do to fix that?’’

Yes,'' smiled Valentine.There is. Once the first processor has sent the message to another, those two can then send messages to two other hosts at the same time. Then there will be four hosts that can send, and so on.’’

``Ah, so you can do the broadcast as a binary tree!’’

``Not really a binary tree – there are some particular features of our network that we should exploit. The interface cards we have allow each processor to simultaneously send messages to any number of the other processors connected to it. However, the messages don’t necessarily arrive at the destinations at the same time – there is a communication cost involved. In general, we need to take into account the communication costs for each link in our network topologies and plan accordingly to minimize the total time required to do a broadcast.’’

Input

The input will describe the topology of a network connecting n processors. The first line of the input will be n, the number of processors, such that 1 <= n <= 100.

The rest of the input defines an adjacency matrix, A. The adjacency matrix is square and of size n x n. Each of its entries will be either an integer or the character x. The value of A(i,j) indicates the expense of sending a message directly from node i to node j. A value of x for A(i,j) indicates that a message cannot be sent directly from node i to node j.

Note that for a node to send a message to itself does not require network communication, so A(i,i) = 0 for 1 <= i <= n. Also, you may assume that the network is undirected (messages can go in either direction with equal overhead), so that A(i,j) = A(j,i). Thus only the entries on the (strictly) lower triangular portion of A will be supplied.

The input to your program will be the lower triangular section of A. That is, the second line of input will contain one entry, A(2,1). The next line will contain two entries, A(3,1) and A(3,2), and so on.

Output

Your program should output the minimum communication time required to broadcast a message from the first processor to all the other processors.

Sample Input

5
50
30 5
100 20 50
10 x x 10

Sample Output

35

题目大意:有个人做了一个32位分布式系统网络,给出n个节点的网络拓扑图(矩阵下三角,满足对称性a[i][j]=a[j][i],x也满足,因为这个wa了一发,失算),然后输入下三角矩阵,并且对角线元素为0,输入有两种一种数字表示i到j的时间费用(就是边权),还有就算x表示i无法发送消息给j(表示边权为无穷),问你从源点1发送给所以点最短距离的最大值是多少?(一开始没看明白这句话:There is. Once the first processor has sent the message to another, those two can then send messages to two other hosts at the same time. Then there will be four hosts that can send, and so on,实际上就是说这个机器是并行的,当我们求出源点到各个点的最短权后,选一个最大的,说明连发给最大权的顶点都发送了,那么其他权小的再送给最大权的时候已经通过并行发送出去了。拿样例说,就是你发信息给2的时候,因为2的最短路是30+5,那么再你发给二的这个过程,源点已经给4,5,3发过信息了,所以最后再发2)
思路:dijkstra跑一遍找最大值。
收获:收获了一个函数
字符串转整形 char ch[10];将里面值转化整形。
int test=atoi(ch)。(头文件cstdlib)
代码:

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

const int maxn=1e3+10;
const int inf=0x3f3f3f3f;
int a[maxn][maxn];
int vis[maxn],dis[maxn];
int n;

void dijkstra(int s){
	memset(vis,0,sizeof(vis));
	memset(dis,88,sizeof(dis));
	for(int i=1;i<=n;i++){
		dis[i]=a[s][i];
	}
	dis[s]=0;vis[s]=1;
	for(int p=1;p<=n-1;p++){
		int minn=inf,k;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis[i]<minn){
				minn=dis[i];
				k=i;
			}
		}
		vis[k]=1;
		for(int i=1;i<=n;i++){
			if(!vis[i]&&dis[i]>dis[k]+a[k][i]){
				dis[i]=dis[k]+a[k][i];
			}
		}
	}
	int maxsum=-98989898;
	for(int i=1;i<=n;i++){
		if(maxsum<dis[i])maxsum=dis[i];
	}
	cout<<maxsum<<endl;
}
int main(){
	while(cin>>n){
	char ch[10];
	memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			if(i==j)continue;
			cin>>ch;
			if(ch[0]!='x'){
				a[j][i]=a[i][j]=atoi(ch);//char []转数字,atoi,marked一下 
			}else{
			    a[j][i]=a[i][j]=inf;
			}
		}
	}
	dijkstra(1); 
}
}

Arbitrage

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 31598 Accepted: 13124

Description

Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.

Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
Input

The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Output

For each test case, print one line telling whether arbitrage is possible or not in the format “Case case: Yes” respectively “Case case: No”.
Sample Input

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0
Sample Output

Case 1: Yes
Case 2: No

题目大意:给出n个货币,和m条货币兑换汇率链,问现有第一种货币资产1,问经过一系列后能否盈利?
思路:求正环即可,因为做过一道类似的题,wa了一发,数组开小了,但是题目n<=30,m没给范围,只能说题目不严谨,改了数组范围ac了,此题还有一个难点:就是将字符转数字,用map记录就好了,我的其他文章好像有写,具体看一下代码把。

#include<iostream>
#include<cstring>
#include<string>
#include<map>
#include<cstring>
using namespace std;
int u[3000],v[3000];
double w[3000];
double dis[3000];
int n,m;
bool bellamn_ford(){
	memset(dis,0,sizeof(dis));
	dis[1]=1;
	for(int i=1;i<=n-1;i++){
		for(int j=1;j<=m;j++){
			if(dis[v[j]]<dis[u[j]]*w[j]){
				dis[v[j]]=dis[u[j]]*w[j];
			}
		}
	}
	for(int j=1;j<=m;j++){
		if(dis[v[j]]<dis[u[j]]*w[j])
		return true;
	}
	return false;
}
int main(){
	int ck=1;
	while(cin>>n&&n){
		map<string,int>st;
		for(int i=1;i<=n;i++){
			string ch;
			cin>>ch;
			st[ch]=i;
		}
		cin>>m;
		for(int i=1;i<=m;i++){
			string str,ch;double r;
			cin>>str>>r>>ch;
			u[i]=st[str];w[i]=r;v[i]=st[ch];
		}
		/*for(int i=1;i<=m;i++){ cout<<u[i]<<"->"<<v[i]<<" :"<<w[i]<<endl;; }*/
		cout<<"Case "<<ck++<<": ";
		if(bellamn_ford()){
			cout<<"Yes"<<endl;
		}else{
			cout<<"No"<<endl;
		}
	}
}

Invitation Cards
Time Limit: 8000MS Memory Limit: 262144K
Total Submissions: 37338 Accepted: 12192

Description

In the age of television, not many people attend theater performances. Antique Comedians of Malidinesia are aware of this fact. They want to propagate theater and, most of all, Antique Comedies. They have printed invitation cards with all the necessary information and with the programme. A lot of students were hired to distribute these invitations among the people. Each student volunteer has assigned exactly one bus stop and he or she stays there the whole day and gives invitation to people travelling by bus. A special course was taken where students learned how to influence people and what is the difference between influencing and robbery.

The transport system is very special: all lines are unidirectional and connect exactly two stops. Buses leave the originating stop with passangers each half an hour. After reaching the destination stop they return empty to the originating stop, where they wait until the next full half an hour, e.g. X:00 or X:30, where ‘X’ denotes the hour. The fee for transport between two stops is given by special tables and is payable on the spot. The lines are planned in such a way, that each round trip (i.e. a journey starting and finishing at the same stop) passes through a Central Checkpoint Stop (CCS) where each passenger has to pass a thorough check including body scan.

All the ACM student members leave the CCS each morning. Each volunteer is to move to one predetermined stop to invite passengers. There are as many volunteers as stops. At the end of the day, all students travel back to CCS. You are to write a computer program that helps ACM to minimize the amount of money to pay every day for the transport of their employees.
Input

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case begins with a line containing exactly two integers P and Q, 1 <= P,Q <= 1000000. P is the number of stops including CCS and Q the number of bus lines. Then there are Q lines, each describing one bus line. Each of the lines contains exactly three numbers - the originating stop, the destination stop and the price. The CCS is designated by number 1. Prices are positive integers the sum of which is smaller than 1000000000. You can also assume it is always possible to get from any stop to any other stop.
Output

For each case, print one line containing the minimum amount of money to be paid each day by ACM for the travel costs of its volunteers.
Sample Input

2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
Sample Output

46
210

首先这是一个好题目学到不少,思路很简单,实现有点困难。
题目大意:在这个电视剧时代几乎没人关注戏剧了,然后有这么一群人想组织一场戏剧给大家看,请了n个学生去发***,然后每个学生分配一个站台,每天早上学生去各自的站台(乘地铁),然后给出各个地铁站之间(来回)的单项价格,问你所有学生一趟来回最小花费是多少?
考点:思路很简单,但是数据范围1e6,用矩阵肯定是存不了的,这里可以采用链式向前星的办法存边,能够很好解决存储问题,然后用堆优化dijkstra ,O(m log n)能够很好的跑完这题。
思路:dijkstra跑出源点到各点最短距离累加起到,然后再跑一遍各点到源点最短距离累加求和就是我们要的答案,我在网上看了很多代码都很麻烦,这里给出一个很容易懂的代码:

#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
typedef long long int ll;
const int maxn = 1e6+10;
ll t, n, m, cnt = 0;
ll sum = 0;
ll x[maxn],y[maxn],z[maxn];
struct edge {
	ll to, w, pre;
};
struct node {
	ll id, d;
	node (ll a,ll b):id(a),d(b){}
	bool operator<(const node &a)const {
		return d > a.d;
	}
};
edge e[maxn];
ll head[maxn];
ll dis[maxn];

void add(ll from, ll to, ll w) {
	e[++cnt].to=to;
	e[cnt].w=w;
	e[cnt].pre=head[from];
	head[from]=cnt; 
}
void dijkstra(ll s) {
	memset(dis, 88, sizeof(dis));
	dis[s] = 0;
	priority_queue<node>st;
	st.push(node(s,0));
	while (!st.empty()) {
		node f = st.top(); st.pop();
		ll u = f.id; ll d = f.d;
		if (d!= dis[u])continue;
		for (int i = head[u]; i; i = e[i].pre) {
			if (dis[e[i].to] > d + e[i].w) {
				dis[e[i].to] = d + e[i].w;
				st.push(node ((ll)e[i].to,(ll)dis[e[i].to]));
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		sum+=dis[i];
	}
}
int main() {
	scanf("%d",&t);
	while (t--) {
		sum=0;
		cnt = 0;
		memset(x,0,sizeof(x));
		memset(y,0,sizeof(y));
		memset(z,0,sizeof(z));
		memset(e,0,sizeof(e));
		memset(head, 0, sizeof(head));
		scanf("%d%d",&n,&m);
		for (int i = 1; i <= m; i++) {
			scanf("%d%d%d",&x[i],&y[i],&z[i]);
			add(x[i], y[i], z[i]);//正向边 
		}
		dijkstra(1);
		memset(e,0,sizeof(e));//清零 
		cnt = 0;
		memset(head, 0, sizeof(head));
		for (int i = 1; i <= m; i++) {
			add(y[i], x[i], z[i]);//反向边 
		}
		dijkstra(1);
		cout<<sum<<endl;
	}
}