OI题库

【题目描述】

放暑假了，LRJ想趁假期提高一下自己的计算机水平，于是他从学校图书馆借了N本计算机科学方面的书，这N本书的编号依次为0～N-1。

读完第i本书，LRJ需要花费time[i]分钟，但是有一些书的内容是相近的，如果第i本书与第j本书内容相近，那么如果LRJ读完了第i本书，再读第j本书的时候只需要floor(time[j]/2)分钟的时间即可（其中floor()表示对括号中的式子进行下取整）；当然，如果LRJ先读完了第j本书，那么再读第i本书的时候只需floor(time[i]/2)的时间。现在你的任务是告诉LRJ，他最少可以用多少分钟读完这N本书。

【输入格式】

第一行有两个整数N（0<=N<=100）和M(0<=M<=N(N-1)/2)。N为书的总数，有M对书内容相近。

接下来有N行，分别表示time[0],time[1],...及time[N-1],(1<=time[i]<=10^5)。

再接下来有M行，每行有两个整数（i,j），表示第i本书与第j本书内容相近。

输出文件以N=0,M=0表示结束。

【输出格式】

对于每组测试数据，输出仅一行，即最少时间。

【样例输入】

2 1
6
10
0 1
3 2
1
2
3
0 1
1 2
3 1
2
4
6
0 1
0 0 

【样例输出】

11
3
10

【提示】

对于第一组数据，如果LRJ读的顺序为（0，1），则总的时间为6+10/2=11，如果读的顺序为（1，0），则总的读书时间为10+6/2=13.

【来源】

在此键入。