Currency Exchange Centers
Input Specification:
Each input file contains one test case. For each case, the first line gives two positive integers N and M (both no more than 1), being the total numbers of currencies and the size of the list of currency exchange center informations, respectively. Then M lines follow, each describes a piece of information in the following format:
C1 C2 Center Fee
where
C1
and C2
are the indices (from 0 to N−1) of the two currencies; Center
is a string of 3 capital English letters representing the name of a center; and Fee
is a positive integer no more than 1. It is guaranteed that at most one exchange center is given for each pair of different currencies. Output Specification:
Print in the first line the total number of currency exchange centered being collected, and the total amount of fees they charge, separated by a space. Then in the following lines, print the centers which must be collected in the same format as the input. The centers must be output in alphabetical order of their names, and if there is a tie, in ascending order of their fees. It is guaranteed that such a solution exists and is unique.
Sample Input:
6 9
4 3 CBC 32
1 5 HSB 43
1 0 HSB 32
0 2 CTB 28
4 2 CBC 19
2 3 CBC 28
0 4 ABC 28
1 2 ABC 32
3 1 CTB 19
Sample Output:
3 137
4 2 CBC 19
2 3 CBC 28
3 1 CTB 19
0 2 CTB 28
1 5 HSB 43
1 #include
2 using namespace std;
3 vector<int> v;
4 set<string> se;
5 struct edge
6 {
7 int v1;
8 int v2;
9 string s;
10 int c;
11 bool operator< (const edge& ee) const
12 {
13 if(c!=ee.c)
14 return c>ee.c;
15 else
16 {
17 auto it=se.find(s);
18 return it!=se.end()?false:true;
19 }
20 }
21 } e;
22 struct cmp
23 {
24 bool operator()(const edge& e1,const edge& e2) const
25 {
26 if(e1.s!=e2.s)
27 return e1.s<e2.s;
28 else
29 return e1.c<e2.c;
30 }
31 };
32 inline int fr(int i)
33 {
34 int ii=i;
35 for(;v[i]!=-1;i=v[i]);
36 if(ii!=i)
37 v[ii]=i;
38 return i;
39 }
40 int main()
41 {
42 // freopen("data.txt","r",stdin);
43 int n,m,k1,k2;
44 char a[4];
45 scanf("%d %d",&n,&m);
46 v.resize(n,-1);
47 priority_queue pq;
48 for(;m--;)
49 {
50 scanf("%d %d",&e.v1,&e.v2);
51 scanf("%s",a);
52 e.s=a;
53 scanf("%d",&e.c);
54 pq.push(e);
55 }
56 vector ve;
57 m=0;
58 for(;ve.size()1;)
59 {
60 e=pq.top();
61 pq.pop();
62 k1=fr(e.v1);
63 k2=fr(e.v2);
64 if(k1!=k2)
65 {
66 v[max(k1,k2)]=min(k1,k2);
67 se.emplace(e.s);
68 ve.emplace_back(e);
69 m+=e.c;
70 }
71 }
72 sort(ve.begin(),ve.end(),cmp());
73 printf("%d %d
",se.size(),m);
74 for(auto i:ve)
75 printf("%d %d %s %d
",i.v1,i.v2,i.s.c_str(),i.c);
76 return 0;
77
78 }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.