SQL数据库编程大赛（第三期）

本期题目：
2011年度itpub数据库技术大会将于4月15日隆重举行。与会人员分布于不同城市(A,B,C,D,....)，每个城市及其会员人数保存在一张表cities(city_name, members)
这些城市及他们之间的通路构成了一张网络交通图。有直接通路的两个城市及其距离保存在表routes之中，所有通路都是双向的，但每条直接通路只用一行记录来表示。
外地的会员将乘坐出租车参加大会，车费等于距离*价格(常数)。本地会员不用考虑交通费。

交通费定义:itpub要为外地会员发放往返的交通补贴，每人每公里2元（双程），在哪个城市举办能够最节省，需要花费多少钱？

问题：选择在哪个城市举行，能够使得会员的总交通费最低？列出这个城市及应发放给其他城市会员的总的交通补助。
输出格式如下：
输出3列数据,按城市名升序排列
举办城市　　TOTAL　　　总费用
举办城市　　来自城市　　　费用
....

例如，假设你求出在A城市最省，总的补助需要发放10000元，其中给B城市的会员要发8000， 给C城市的会员要发2000
输出

CODE:

A TOTAL 10000
A B 8000
A C 2000

如果存在在多个城市办会交通费用相同，则都列出,按城市名升序排列
例如，假设你求出在A,B城市最省，需要发10000元，如果在A办，B城市的会员8000， C城市的会员2000，如果在B办，A城市的会员8000， C城市的会员2000，
输出

CODE:

A TOTAL 10000
A B 8000
A C 2000
B TOTAL 10000
B A 8000
B C 2000

表结构和样例数据如下，样例数据供参考，评委将用多组数据验证你的解答。表结构不能变动，不按此表结构答题的不得分。

CODE:

CREATE TABLE cities (
city_nameVARCHAR2(10) PRIMARY KEY
,members NUMBER
);
INSERT INTO cities
(
SELECT 'A' ,20 FROM dual union
SELECT 'B' ,31 FROM dual union
SELECT 'C' ,23 FROM dual union
SELECT 'D' ,42 FROM dual union
SELECT 'E' ,25 FROM dual union
SELECT 'F' ,29 FROM dual union
SELECT 'G' ,32 FROM dual union
SELECT 'H' ,45 FROM dual union
SELECT 'I' ,50 FROM dual union
SELECT 'J' ,32 FROM dual union
SELECT 'K' ,22 FROM dual
);
commit;

CREATE TABLE routes (
city1 VARCHAR2(10)
,city2 VARCHAR2(10)
,distance NUMBER
,PRIMARY KEY (city1,city2)
,CONSTRAINT check_cities CHECK (city1<city2) ---- 为了防止同一条通路被插入两遍
);
INSERT INTO routes
(
SELECT 'A' ,'B' , 71 FROM dual union
SELECT 'A' ,'C' , 80 FROM dual union
SELECT 'A' ,'D' , 80 FROM dual union
SELECT 'A' ,'E' , 66 FROM dual union
SELECT 'A' ,'F' , 86 FROM dual union
SELECT 'C' ,'G' ,112 FROM dual union
SELECT 'D' ,'G' , 60 FROM dual union
SELECT 'G' ,'H' ,102 FROM dual union
SELECT 'G' ,'I' , 91 FROM dual union
SELECT 'G' ,'J' ,133 FROM dual union
SELECT 'G' ,'K' ,127 FROM dual union
SELECT 'C' ,'D' , 79 FROM dual union
SELECT 'C' ,'H' ,155 FROM dual union
SELECT 'C' ,'E' ,119 FROM dual union
SELECT 'B' ,'D' , 52 FROM dual union
SELECT 'D' ,'I' , 44 FROM dual union
SELECT 'B' ,'L' , 41 FROM dual union
SELECT 'J' ,'L' ,201 FROM dual union
SELECT 'B' ,'F' , 79 FROM dual union
SELECT 'H' ,'K' , 38 FROM dual union
SELECT 'J' ,'K' , 81 FROM dual
);
commit;

数据库平台：适用Oracle、MS SQL Server，版本（Oracle推荐10gr2（包含）以上版本、MS SQL Sever推荐2008版本）

原文见：http://www.itpub.net/thread-1408182-1-1.html

参赛者答案：http://www.itpub.net/thread-1415335-1-1.html

我提交的答案：

/*
Oracle11gR2，使用递归with语法,运行时间0.05秒
allroutes 根据routes得出包括反方向的所有路径组合，
s子句是生成各个城市间的不同路径列表:
rn的作用主要用于判断循环,
root表示出发城市,
city2表示目标城市,
sum_dis 表示距离,
path表示路径，里面的内容如'A-B-C-D'这样的

where条件中instr(s.path,a.city2)<=0作用是不出现回路，即当发现a.city2（新路径的终点城市）已经在上一路径列表里则退出这一支路的递归
s.sum_dis+a.DISTANCE<
(select nvl(max(r.DISTANCE),999999) from routes r
where (s.root=r.city1 and a.city2=r.city2) or (s.root=r.city2 and a.city2=r.city1)
)
上面这个条件是取消路径小于routes中直线路径长度的后续检测，这里没有使用前面定义的allroutes是为了使用索引进行性能优化
grouping sets(city_name,(city_name,city2)这个子句用于分组统计总成本及各城市间成本。
*/

with allroutes as (select rownum rn,city1,city2,distance from routes
union all select rownum rn,city2,city1,distance from routes),
s(rn,root,city2,sum_dis,path) as(
  select rn,city1 root,city2,DISTANCE sum_dis,city1||'-'||city2 path from allroutes
  union all
  select a.rn,s.root,a.city2,s.sum_dis+a.DISTANCE sum_dis,s.path||'-'||a.city2 path
  from s,allroutes a
  where a.city1=s.city2 and instr(s.path,a.city2)<=0
  and s.sum_dis+a.DISTANCE<
    (select nvl(max(r.DISTANCE),999999) from routes r 
     where (s.root=r.city1 and a.city2=r.city2) or (s.root=r.city2 and a.city2=r.city1)
    )
)
cycle rn set cycle_flag to 'Y' default 'N'
select root,nvl(city_name,'TOTAL'), sum(money) from (
  select a.*,rank() over(order by sum_money) sum_money_rank from (      
    select b.city_name,a.root,b.members*a.sum_dis*2 money,sum(b.members*a.sum_dis*2) over(partition by a.root) sum_money from (      
      select root, city2,min(sum_dis) sum_dis from s where cycle_flag='N' group by root, city2 --取得各城市间最小路径值
    ) a,cities b where a.city2=b.city_name
  )a
) where sum_money_rank=1 --得到费用最小的举办城市
group by grouping sets(root,(root,city_name)) --分组显示
order by root,city_name nulls first --TOTAL放最前面
;

/*
Oracle10gR2，使用connect by语法,运行时间0.3秒
allroutes 根据routes得出包括反方向的所有路径组合,
CONNECT_BY_ROOT(city1) root表示出发城市,
city2表示目标城市,
sum_money_str表示路径距离的一个字符串，里面的内容如'000+080+082+091'这样的,
nocycle 用于终止循环路径,
CONNECT_BY_ROOT(city1) <> city2 优化用,当路径回到根节点时退出，
+use_merge(a,b) 优化用
与子查询select rownum rn from dual connect by rownum < (select count(*) from cities) 关联，用于计算sum_money_str的值
sum(substr(a.sum_money_str, (b.rn) * 4 + 1, 3)) distance用于计算sum_money_str值
grouping sets(city_name,(city_name,city2)这个子句用于分组统计总成本及各城市间成本。
*/

select root,nvl(city_name,'TOTAL'), sum(money)
from (select city_name, root, money, rank() over(order by sum_money) sum_money_rank
      from (select b.city_name,a.root,b.members * a.distance * 2 money,sum(b.members * a.distance * 2) over(partition by a.root) sum_money
         from (select root,city2,min(distance) distance
               from (select /*+use_merge(a,b)*/ a.root,a.city2,rn1,sum(substr(a.sum_money_str, (b.rn) * 4 + 1, 3)) distance
                     from (select rownum rn1,CONNECT_BY_ROOT(city1) root,city2,distance,'000' ||SYS_CONNECT_BY_PATH(lpad(distance,3,'0'),'+') sum_money_str,level len                        
                           from (select city1,city2,distance from routes
                                union all
                                select city2,city1,distance from routes) t
                           connect by nocycle
                           city1 = prior city2 and CONNECT_BY_ROOT(city1) <> city2) a,
                           (select rownum rn from dual connect by rownum < (select count(*) from cities)) b
                     where b.rn <= a.len group by a.root, a.city2, rn1)
                group by root,city2) a,cities b
      where a.city2 = b.city_name))
where sum_money_rank=1 --得到费用最小的举办城市
group by grouping sets(root,(root,city_name)) --分组显示
order by root,city_name nulls first --TOTAL放最前面
;

以下是结果：
ROOT NVL(CITY_NAME,'TOTAL') SUM(MONEY)
---------- ---------------------- ----------
D TOTAL 68356
D A 3200
D B 3224
D C 3634
D E 7300
D F 7598
D G 3840
D H 14580
D I 4400
D J 12352
D K 8228

解题思路：见上面的备注。

评委点评：where (s.root=r.city1 and a.city2=r.city2) or (s.root=r.city2 and a.city2=r.city1))
条件的优化思路很明确。性能很好。
但是此答案也存在瑕疵，11g版本答案能正确输出多种选择和多次转乘，但一个城市的名称包含另外一个城市名称时无法输出正确结果。另：10g版本答案在某些测试数据下输出错误。

个人分析：

1、这道题主要是考一个图路径的算法，我算法不好，所以也不管理论的东西，按自己的理解去做。

2、因为看到前两期有许多人用11gR2新的with递归语法，所以也尝试学习一下。感觉功能比以前强大，不过语法规则设计得太差，估计是ORACLE公司新来的人设计，只是实现了功能，没考虑开发人员的思维习惯，所以不看参考手册基本上用不来。

3、题目好像是说要满足10gR2的版本，不清楚为什么用11gR2的新语法不扣分，反而加分，这不符合实际应用，毕竟实战中通用性很重要。

4、如评委所说，未考虑到城市名称中有字符名含的问题，原因是提供的测试数据不存在包含的现象，所以忽略了，实际当中还是存在的。

5、SQL整体性能还不错，但是大数据量时估计性能不好。

总体来说，这期得分还算合理，个人感觉第4名（3-7）很精彩，根据图论基础算法使用Oracle10g的MODEL语法解题。