汤姆斯的天堂梦(par)
【问题描述】
汤姆斯生活在一个等级为0的星球上。那里的环境极其恶劣，每天12小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为N的星球上天堂般的生活。
有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。
汤姆斯预先知道了从0等级星球去N等级星球所有的航线和需要支付（或者可以得到）的金钱，他想寻找一条价格最低（甚至获得金钱最多）的航线。
【输入】
第一行一个正整数N(N≤100)，接下来的数据可分为N个段落每段的第一行一个整数Ki(Ki≤100)，表示等级为i的星球有Ki个。
接下来的Ki中第Tij行依次表示与等级为i，编号为i的星球相连的等级为i-l的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过1000）。
每行以0结束，每行的航线数≤100。
【输出】
输出所需（或所得）费用。正数表示支出，负数表示收益。
【输入样例】
3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 -20 0
【输出样例】
-1
【数据范围】
对于100%的数据N≤100 Ki≤100。
【样例解释】
如右图
=================================
可能有双边...三边....四边...n边...这个要判断...
=======================
{ID:jie19952PROG:LANG:PASCAL}varn:longint;map:array[0..100,0..100,0..100]of longint;bool_map:array[0..100,0..100,0..100]of boolean;map_num:array[0..100]of longint;//表示每层有多少个..f:array[0..100,0..100]of longint;procedure init;beginassign(input,'par.in');assign(output,'par.out');reset(input); rewrite(output);end;procedure terminate;beginclose(input); close(output);halt;end;procedure main;vari,j,k:longint;x,t:longint;ans:longint;beginreadln(n);fillchar(bool_map,sizeof(bool_map),false);map_num[0]:=1;for i:=1 to n dobeginreadln(map_num[i]);//表示第i层有多少个..for j:=1 to map_num[i] dobeginread(x);while x<>0 dobeginread(t); //表示第i层的第j个与i-1层的第x个if bool_map[i,j,x] thenbeginif t<map[i,j,x] then map[i,j,x]:=t;endelse map[i,j,x]:=t;bool_map[i,j,x]:=true;read(x);end;end;end;f[0,1]:=0;for i:=1 to n dobeginfor j:=1 to map_num[i] dobeginf[i,j]:=maxlongint;for k:=1 to map_num[i-1] doif bool_map[i,j,k] thenbeginif f[i,j]>f[i-1,k]+map[i,j,k] thenf[i,j]:=f[i-1,k]+map[i,j,k];end;end;end;ans:=maxlongint;for i:=1 to map_num[n] doif f[n,i]<ans then ans:=f[n,i];writeln(ans);end;begininit;main;terminate;end.
