测试：
题目：
Input
Output
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
题解：floyd可做，f[M][M]的清零，注意long long的%lld,用char数组要用strcmp进行比较！对大于小于的理解！！
爱吃代码：
1 #include<cstdio> 2 #include<cstring> 3 #define esp 0.000001 4 #define M 500 5 using namespace std; 6 int n,m,bb,cc,cs,tmp; 7 double f[M][M],x; 8 char b[M],c[M],a[M][M]; 9 int main() 10 { 11 while(~scanf("%d",&n)) 12 { 13 cs++; 14 if(n==0) 15 break; 16 for(int i=0;i<n;i++) 17 { 18 scanf("%s",a[i]); 19 } 20 for(int i=0;i<n;i++) 21 { 22 for(int j=0;j<n;j++) 23 f[i][j]=0.0; 24 } 25 scanf("%d",&m); 26 for(int i=0;i<m;i++) 27 { 28 scanf("%s%lf%s",b,&x,c); 29 for(int i=0;i<n;i++) 30 { 31 if(strcmp(b,a[i])==0) 32 bb=i; 33 if(strcmp(c,a[i])==0) 34 cc=i; 35 } 36 f[bb][cc]=x; 37 } 38 /*for(int i=0;i<n;i++) 39 { 40 for(int j=0;j<n;j++) 41 printf(" %lf \n",f[i][j]); 42 }*/ 43 for(int k=0;k<n;k++) 44 { 45 for(int i=0;i<n;i++) 46 { 47 for(int j=0;j<n;j++) 48 { 49 if(f[i][k]*f[k][j]>f[i][j]) 50 f[i][j]=f[i][k]*f[k][j]; 51 52 } 53 } 54 } 55 //printf("\n"); 56 tmp=0; 57 for(int i=0;i<n;i++) 58 { 59 //printf(" %lf ",f[i][i]); 60 if(f[i][i]-1>esp) 61 { 62 printf("Case %d: Yes\n",cs); 63 tmp=1; 64 break; 65 } 66 67 } 68 if(tmp==0) 69 printf("Case %d: No\n",cs); 70 71 } 72 return 0; 73 }
2.
Input输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。
Output如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。
Sample Input
6 xiasha westlake xiasha station 60 xiasha ShoppingCenterofHangZhou 30 station westlake 20 ShoppingCenterofHangZhou supermarket 10 xiasha supermarket 50 supermarket westlake 10 -1
Sample Output
50 Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake 虽然偶尔会迷路，但是因为有了你的帮助 **和**从此还是过上了幸福的生活。 ――全剧终――
题解：要用map（映射）去存字符串！，注意格式和清零！！！cnt now ans 清零，a，b不要写反！m，n不要写反！！！
爱吃代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<map> 5 #define inf 0x3f3f 6 #define M 300 7 using namespace std; 8 int n,f[M][M],aa,bb,ss,tt,w,cnt; 9 char vis[M][M],a[M],b[M],s[M],t[M]; 10 map<string,int>m; 11 int main() 12 { 13 while(~scanf("%d",&n)) 14 { 15 if(n==-1) 16 break; 17 cnt=1; 18 m.clear(); 19 scanf("%s%s",s,t); 20 if(strcmp(s,t)==0) 21 m[s]=m[t]=cnt++; 22 else 23 { 24 m[s]=cnt++; 25 m[t]=cnt++; 26 } 27 ss=m[s]; 28 tt=m[t]; 29 for(int i=0;i<200;i++) 30 for(int j=0;j<200;j++) 31 { 32 if(i==j) 33 f[i][j]=0; 34 else f[i][j]=inf; 35 } 36 37 for(int i=0;i<n;i++) 38 { 39 scanf("%s%s%d",a,b,&w); 40 /* 41 aa=-1; 42 bb=-1; 43 for(int j=0;j<155;j++) 44 { 45 if(strcmp(a,vis[j])==0) 46 aa=j; 47 if(strcmp(b,vis[j])==0) 48 bb=j; 49 } 50 51 if(aa<0) 52 { 53 aa=cnt; 54 strcpy(vis[cnt++],a); 55 } 56 if(bb<0) 57 { 58 bb=cnt; 59 strcpy(vis[cnt++],b); 60 }*/ 61 if(!m[a]) m[a]=cnt++; 62 if(!m[b]) m[b]=cnt++; 63 if(w<f[m[a]][m[b]]) 64 f[m[a]][m[b]]=f[m[b]][m[a]]=w; 65 } 66 for(int k=1;k<=cnt;k++) 67 { 68 for(int i=1;i<=cnt;i++) 69 { 70 for(int j=1;j<=cnt;j++) 71 { 72 if(f[i][k]+f[k][j]<f[i][j]) 73 f[i][j]=f[i][k]+f[k][j]; 74 } 75 } 76 } 77 if(ss==tt) 78 printf("0\n"); 79 else if(f[ss][tt]<inf) 80 printf("%d\n",f[ss][tt]); 81 82 else 83 printf("-1\n"); 84 } 85 return 0; 86 }
3.
InputThe 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.
OutputFor 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
题解：又一道de了很久很久的bug，思路很重要，先正着存，然后spfa从1出发，然后算出所用的dis【i】，然后再倒着存，还是从1出发算dis【i】
注意：inf的值也不易太大，如果太大要超出，cnt要从1开始，省的每次都有错，spfa注意dis【x】=0，注意n，m的区别；
爱吃代码：
1 #include<cstdio> 2 #include<queue> 3 #define inf 1e8 4 #define M 2001000 5 using namespace std; 6 long long cnt=1,n,m,u[M],v[M],w[M],head[M],dis[M],t,ans,vis[M]; 7 struct hhh 8 { 9 long long to,nxt,w; 10 }e[M]; 11 queue<long long >q; 12 void add(long long u,long long v,long long w) 13 { 14 e[cnt].to=v; 15 e[cnt].w=w; 16 e[cnt].nxt=head[u]; 17 head[u]=cnt++; 18 } 19 void spaf(int x) 20 { 21 for(int i=0;i<=n;i++) 22 { 23 if(x==i) 24 dis[i]=0; 25 else dis[i]=inf; 26 } 27 //printf("a%da ",dis[1]); 28 vis[x]=1; 29 q.push(x); 30 int r,v; 31 while(!q.empty()) 32 { 33 r=q.front(); 34 q.pop(); 35 for(int i=head[r];i;i=e[i].nxt) 36 { 37 v=e[i].to; 38 if(dis[v]>dis[r]+e[i].w) 39 { 40 dis[v]=dis[r]+e[i].w; 41 //printf("aaa"); 42 if(vis[v]==0) 43 vis[v]=1,q.push(v); 44 } 45 } 46 vis[r]=0; 47 } 48 49 } 50 int main() 51 { 52 scanf("%lld",&t); 53 while(t--) 54 { 55 scanf("%lld%lld",&n,&m); 56 cnt=1; 57 for(int i=0;i<=n;i++) 58 { 59 head[i]=0,e[i].to=e[i].nxt=e[i].w=0; 60 } 61 for(int i=1;i<=m;i++) 62 { 63 scanf("%lld%lld%lld",&u[i],&v[i],&w[i]); 64 add(u[i],v[i],w[i]); 65 } 66 ans=0; 67 spaf(1); 68 for(int i=1;i<=n;i++) 69 { 70 ans+=dis[i]; 71 } 72 //printf(" %d ",ans); 73 for(int i=0;i<=m;i++) 74 { 75 head[i]=0; 76 } 77 cnt=1; 78 for(int i=1;i<=m;i++) 79 { 80 add(v[i],u[i],w[i]); 81 } 82 spaf(1); 83 for(int i=1;i<=n;i++) 84 { 85 ans+=dis[i]; 86 } 87 printf("%lld\n",ans); 88 } 89 return 0; 90 }
4.
InputThe input consists of multiple test cases. The first line of each test case contains two integers, n(0 < n <= 10000), m(0 <= m <= 100000), which are the number of the vertexes and the number of the edges. The next m lines, each line consists of three integers, u, v, c, which means there is an edge with value c (0 < c <= 10000) between u and v. You can assume that there are no loop and no multiple edges.
The last test case is followed by a line containing two zeros, which means the end of the input.
OutputOutput the sum of the value of the edges of the maximum pesudoforest.
Sample Input
3 3 0 1 1 1 2 1 2 0 1 4 5 0 1 1 1 2 1 2 3 1 3 0 1 0 2 2 0 0
Sample Output
3 5
不会
5.
Input
Output
Sample Input
2 3 3 1 2 1 2 3 2 3 1 3 4 4 1 2 2 2 3 2 3 4 2 4 1 2
Sample Output
3 Not Unique!
题解：最小生成树，然后是唯一的，记录有哪些路径在最小生成树中，然后for不要其中一条去看是否可以形成值相同的最小生成树；
注意：ans cnt 清零，特判n==1&&m==0 跑两趟 区分m和n
爱吃代码
1 #include<cstdio> 2 #include<algorithm> 3 #define M 1020 4 #define N 10100 5 using namespace std; 6 int t,n,m,a,b,c,ww,ans,fa[M],cnt,aa,now,q,no,vis[M],ans1,ans2; 7 struct hhh 8 { 9 int f,to,w; 10 }e[N]; 11 int finda(int x) 12 { 13 if(x==fa[x]) return x; 14 return fa[x]=finda(fa[x]); 15 } 16 bool cmp(hhh a,hhh b) 17 { 18 if(a.w==b.w) return a.to<b.to; 19 return a.w<b.w; 20 } 21 int kruskal() 22 { 23 for(int i=0;i<=n;i++) 24 fa[i]=i; 25 ans=0; 26 cnt=0; 27 for(int i=1;i<=m;i++) 28 { 29 a=finda(e[i].f); 30 b=finda(e[i].to); 31 if(a==b) continue; 32 if(q==0 && i==no) continue; 33 ww=e[i].w; 34 ans+=ww; 35 fa[a]=b; 36 cnt++; 37 if(q==1) vis[now++]=i; 38 if(cnt==n-1) break; 39 } 40 if(cnt==n-1) return ans; 41 return -1; 42 } 43 int main() 44 { 45 scanf("%d",&t); 46 while(t--) 47 { 48 scanf("%d%d",&n,&m); 49 aa=1; 50 now=0; 51 for(int i=0;i<=n;i++) 52 fa[i]=i; 53 for(int i=1;i<=m;i++) 54 scanf("%d%d%d",&e[i].f,&e[i].to,&e[i].w); 55 sort(e+1,e+m+1,cmp); 56 q=1; 57 ans1=kruskal(); 58 if(ans1==-1) ans1=0; 59 q=0; 60 for(int i=0;i<now;i++) 61 { 62 no=vis[i]; 63 ans2=kruskal(); 64 if(ans2==ans1) aa=0; 65 } 66 if(n==1 || m==0) 67 printf("0\n"); 68 else if(aa==1) 69 printf("%d\n",ans1); 70 else printf("Not Unique!\n"); 71 } 72 return 0; 73 }
6.
InputEach case there are two numbers in the first row, N and M, separated by a single space, the number of towns,and the number of roads between the towns. 1 ≤ N ≤ 1000, 1 ≤ M ≤ N*(N-1)/2. The cities are markedwith numbers from 1 to N, Mirko is located in city 1, and Marica in city N.
In the next M lines are three numbers A, B and V, separated by commas. 1 ≤ A,B ≤ N, 1 ≤ V ≤ 1000.Those numbers mean that there is a two-way road between cities A and B, and that it is crossable in V minutes.OutputIn the first line of the output file write the maximum time in minutes, it could take Marica to come to Mirko.Sample Input
5 6 1 2 4 1 3 3 2 3 1 2 4 4 2 5 7 4 5 1 6 7 1 2 1 2 3 4 3 4 4 4 6 4 1 5 5 2 5 2 5 6 5 5 7 1 2 8 1 4 10 2 3 9 2 4 10 2 5 1 3 4 7 3 5 10
不会
7.
Input
Output
Sample Input
1 4 10000 3 2 2 8000 3 5000 1000 2 1 4 200 3000 2 1 4 200 50 2 0
Sample Output
5250
不会
8.
InputThe first line contains an integer T,which is the number of test cases.
For each testcase:
The first line contains two integers N and M,1<=N<=3000,1<=M<=70000,the cities is numbered from 1 to N and the U.S. landed on city 1 while the capital of the Mars is city N.
The next M lines describes M paths on the Mars.Each line contains three integers ai,bi and wi,indicates there is a unidirectional path form ai to bi lasts wi minutes(1<=wi<=10^8).
The next N lines describes N citys,the 1+M+i line starts with a integer li,followed with li integers, which is the number of cities has a echantment generator protects city i.
It‘s guaranteed that the city N will be always reachable.OutputFor each case,print a line with a number indicating the minimium time needed to enter the capital of the Mars.Sample Input
1 6 6 1 2 1 1 4 3 2 3 1 2 5 2 4 6 2 5 3 2 0 0 0 1 3 0 2 3 5
Sample Output
5
Hint
The Map is like this: We can follow these ways to achieve the fastest speed: 1->2->3,1->2->5,1->4->6.
不会
9.
InputThe first line contains an integer t meaning that there are t test cases(t <= 10).
For each test case:
The first line is an integer n meaning that there are n cities(2 < n <= 1000).
Then n lines follow. Each line contains three integers X, Y and P ( 0 <= X, Y <= 1000, 0 < P < 100000). (X, Y) is the coordinate of a city and P is the population of that city.
It is guaranteed that each city has a distinct location.OutputFor each test case, print a line indicating the above mentioned maximum ratio A/B. The result should be rounded to 2 digits after decimal point.Sample Input
2 4 1 1 20 1 2 30 200 2 80 200 1 100 3 1 1 20 1 2 30 2 2 40
Sample Output
65.00 70.00
不会
原文：https://www.cnblogs.com/lllllllm/p/12258468.html