チャレンジプログラミングコンテスト2.5練習問題:Mr.Rito Post Office Aizu-2200

5757 ワード
遠く離れた島の郵便局で働いているプログラマーです.あなたが住んでいる地域にはいくつかの島が含まれています.島ごとに1つ以上の港町があります.それらのほかに、他の町があるかもしれません.船で一つの島から別の島に行かなければなりません.陸地ルートで島を回ることができますが、海上ルートを使うともっと速くなることがあります.近年の郵便局の私有化に伴い、全国各地の郵便配達員の数が減少し、コストを削減している.辺鄙な島の郵便局も例外ではないので、Ritoさんは唯一の郵便配達員です.郵便局は収集と伝達を担当する地域が大きいため、収集と伝達だけが困難な任務である.そのため、Rito氏は、効率的な収集と納品を支援するために助けを求めています.あなたの任務は、Ritoさんが従う町の送迎順序に応じて、最短のルートを探すプログラムを作成することです.Rito氏は、指定された順序以外の順序で収集と納品を実行することはできません.しかし、ある町や村から別の町や村に移ると、別の町や村を通り抜けることができます.また、Ritoさんには島を迂回できる船があります.たとえば、A町、B町、C村の出荷順序を指定すると、どの町または村を通じてA町からB町まで出荷できます.この場合、C村を通る可能性がありますが、出荷順序と配送順序を維持するためには、一度にB町に行って出荷と配送を実行し、再びC村を訪問して出荷と配送を行う必要があります.海路を通って町Aから町Bまで、陸路を通って町Bから町Cまで行くと、船は町Bに残ります.そのため、次の航海ルートを使いたい場合は、B町に戻る必要があります.1つの町や村で何度も収集して運ぶ必要があるかもしれません.例えば、都市A、農村B、都市C、農村Bの出荷順序および納品順序を与えることができる.現在、B村に従わずにA町からC町に行くと、すぐにC町で荷物を運ぶことができません.これは第一村Bでの収集と交付がまだ完了していないためである.C町で収集して交付した後、B村を訪問し、まだB村の最初の収集と交付を終えていない.リトルさんはいつも港で船を鎮めています.Ritoさんはベテランなので、旅行時間以外の収集や納品にかかる時間を無視することができます.また、最後の町や村で収集と納品が完了する時間だけが問題であり、船を元の位置に戻して郵便局に戻る時間を考慮する必要はありません.
Input
入力には複数のデータセットが含まれます.各データセットのフォーマットは次のとおりです.
N Mx1 y1 t1 sl1x2 y2 t2 sl2...xM yM tM slMRz1 z2 ... zR
データ・セットのすべてのエントリは負の整数ではありません.1行の入力項目はスペースで区切られます.1行目は陸地と海洋ネットワークの規模を指定します.N(2≦N≦200)は町または村の数である.各町または村には1からNまでの唯一の番号が割り当てられている.M(1≦M≦10000)は陸地と海上航路の総数である.2から1+M行目は陸路または海路の記述である.xiとyi(1≦xi,yi≦N)は両端の町または村の数を表す.ti(1≦ti≦1000)陸地または海上航路の旅行時間を表す.sliは「L」または「S」であり、Lは土地を表し、Sは海洋を表す.2つの町または村を直接結ぶ陸路または海上路線は1つ以上である可能性がある.各陸地または海洋路線は双方向であり、すなわちいずれかの方向に移動することができる.M+2行のR(1≦R≦1000)Rito氏が処理した宛先と送付先の数を示す.M+3行において宛先町ziのR数ziを収集・納入の順に並べた(1≦zi≦N).初期状態では、Ritoさんとこの船は港町z 1に位置しています.初期状態からターゲット町または村に移動するには、常に何らかの方法で移動できます.入力の最後は、2つのゼロを含む行で表され、2つのゼロの間にスペースで区切られています.
Output
各入力データセットについて、Ritoさんが指定した受入と納品順に町を巡回するのに必要な最短旅行時間を見つけて、一行に出力します.
Sample Input 
3 3
1 2 5 L
1 2 7 S
2 3 11 S
3
1 2 3
5 5
1 2 15 L
2 3 10 L
4 5 7 L
1 3 30 S
3 4 100 S
5
1 3 5 4 1
0 0

Output for the Sample Input 
18
269
          dp，      （N  200），O(V3)   （  8s）。
           ，     Floyd      ，             ，           min_land,min_sea    v u          。
        ，              (ord[i]  i        ，          R，ord[i]   R  i   ）：
      ，    ，                      ，                            ，           ，               ，                  ，   dp[i][j]       i    （     i   ，      ord    i  ），       j   ，  dp[i][j] =   dp[i-1][k]      （              ，       k   ），  dp[i - 1][k] +   i-1     k        min_land[ord[i - 1]][k]      j     min_sea[k][j],    j   i  min_land[j][ord[i]]。         i     ，           j  i，      i-1 i  i k，  k j，  j i，     i-1 k             i-1 i，i  k   （  i-1 k         ），      i。
      j i    ，    dp[i][j]        i          j，          ，   ，         j ，    ，      。
         j==k ，       ，       k    ，                        dp[i-1][k] + min_land[ord[i - 1]][ord[i]]（ ：  i==k）。
                 ：
　　  j != k: dp[i][j] = min(dp[i - 1][k] + min_land[ord[i - 1]][k] + min_sea[k][j] + min_land[j][i], dp[i][j]);
　　　  j == k: dp[i][j] = min(dp[i - 1][k] + min_land[ord[i - 1]][ord[i]], dp[i][j]);
AC  （  https://www.cnblogs.com/ibilllee/p/9239869.html）：
#include 
#include 
#include 
using namespace std;
//     int   ，  longlong
const long long INF = 0x1f3f3f3f3f3f3f3f;//    4*INF    longlong   
long long dp[1005][205];//dp[i][j]:   i   （         i，    R     ）    j               
long long min_land[1005][1005];//v u        
long long min_sea[1005][1005];//v u        
int ord[1005];//R     ，  i          
char temp[10];//   L  S
int main(void) 
{
	int n, m, r;
	int s, e, t;
	while(scanf("%d %d", &n, &m) && n + m)
	{
		long long ans = INF;
		fill(min_land[0] , min_land[0] + 1005 * 1005, INF);
		fill(min_sea[0] , min_sea[0] + 1005 * 1005, INF);
		fill(dp[0] , dp[0] + 1005 * 205, INF);
		for(int i = 1; i <= n; i++)//Floyd    min_[i][i] = 0，   INF
		{
			min_land[i][i] = min_sea[i][i] = 0;
		}
		for(int i = 0; i < m; i++)
		{
			scanf("%d %d %d %s", &s, &e, &t, temp);
			if(temp[0] == 'L')
			{
				min_land[s][e] = t;
				min_land[e][s] = t;
			}
			else
			{
				min_sea[s][e] = t;
				min_sea[e][s] = t;
			}
		}
        //Floyd  
		for(int k = 1; k <= n; k++)
			for(int i = 1; i <= n; i++)
				for(int j = 1; j <= n; j++)
				{
					min_land[i][j] = min(min_land[i][j], min_land[i][k] + min_land[k][j]);
					min_sea[i][j] = min(min_sea[i][j], min_sea[i][k] + min_sea[k][j]);
				}
		scanf("%d", &r);
		for(int i = 1; i <= r; i++)
			scanf("%d", &ord[i]);
		dp[1][ord[1]] = 0;//        1 ，   ，        
		for(int i = 2; i <= r; i++)//       
			for(int j = 1; j <= n; j++)//           
				for(int k = 1; k <= n; k++)//              （            1 n    ，           
				{
					if(k != j)
						dp[i][j] = min(dp[i][j], dp[i - 1][k] + min_land[ord[i - 1]][k] + min_sea[k][j] + min_land[j][ord[i]]);
					else
						dp[i][j] = min(dp[i][j], dp[i - 1][j] + min_land[ord[i - 1]][ord[i]]);
				}
		for(int i = 1; i <= n; i++)// dp[r][] ，               ，      1 n   ，       ，         
			ans = min(ans, dp[r][i]);
		printf("%lld
", ans);
	}
	return 0;
}    

 
 
　　
 
 
 
Python入門——小甲魚Day 2
各種OSでのネットワーク再起動コマンド一覧