生活随笔
收集整理的這篇文章主要介紹了
Week7 B - TT 的旅行日记
小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
Week7 B - TT 的旅行日記
今天他在 B 站上開(kāi)啟了一次旅行直播，記錄他與魔法貓?jiān)谶餍锹糜螘r(shí)的奇遇。 TT 從家里出發(fā)，準(zhǔn)備乘坐貓貓快線前往喵星機(jī)場(chǎng)。貓貓快線分為經(jīng)濟(jì)線和商業(yè)線兩種，它們的速度與價(jià)錢(qián)都不同。當(dāng)然啦，商業(yè)線要比經(jīng)濟(jì)線貴，TT 平常只能坐經(jīng)濟(jì)線，但是今天 TT 的魔法貓變出了一張商業(yè)線車(chē)票，可以坐一站商業(yè)線。假設(shè) TT 換乘的時(shí)間忽略不計(jì)，請(qǐng)你幫 TT 找到一條去喵星機(jī)場(chǎng)最快的線路，不然就要誤機(jī)了！
輸入
下一行包含一個(gè)整數(shù) M (1 ≤ M ≤ 1000)，即經(jīng)濟(jì)線的路段條數(shù)。
接下來(lái)有 M 行，每行 3 個(gè)整數(shù) X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 100)，表示 TT 可以乘坐經(jīng)濟(jì)線在車(chē)站 X 和車(chē)站 Y 之間往返，其中單程需要 Z 分鐘。
下一行為商業(yè)線的路段條數(shù) K (1 ≤ K ≤ 1000)。
接下來(lái) K 行是商業(yè)線路段的描述，格式同經(jīng)濟(jì)線。
所有路段都是雙向的，但有可能必須使用商業(yè)車(chē)票才能到達(dá)機(jī)場(chǎng)。保證最優(yōu)解唯一。
輸出
本題不忽略多余的空格和制表符，且每一組答案間要輸出一個(gè)換行
輸入樣例
4 1 4
4
1 2 2
1 3 3
2 4 4
3 4 5
1
2 4 3
輸出樣例
1 2 4
2
5
解題思路 Code
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
const int inf
= 5 * 1e8 ;
const int maxnu
= 2500 ;
using namespace std
;
int n
, s
, e
;
int m
, k
;
struct Edge
{ int to
= 0 ; int next
= 0 ; int v
= 0 ;
} edge
[ maxnu
] ;
int head
[ maxnu
] ;
int tot
;
int dis
[ 3 ] [ maxnu
] ;
int vis
[ maxnu
] ;
int fro
[ 3 ] [ maxnu
] ;
void add ( int x
, int y
, int v
) { edge
[ ++ tot
] . to
= y
; edge
[ tot
] . next
= head
[ x
] ; edge
[ tot
] . v
= v
; head
[ x
] = tot
;
}
priority_queue
< pair
< int , int > > q
;
void dijkstra ( int s
, int z
, int r
) { while ( q
. size ( ) ) q
. pop ( ) ; memset ( vis
, 0 , sizeof ( vis
) ) ; for ( int i
= 1 ; i
<= n
; i
++ ) { dis
[ z
] [ i
] = inf
; } dis
[ z
] [ s
] = 0 ; fro
[ r
] [ s
] = - 1 ; q
. push ( make_pair ( 0 , s
) ) ; while ( q
. size ( ) ) { int x
= q
. top ( ) . second
; q
. pop ( ) ; if ( vis
[ x
] ) continue ; vis
[ x
] = 1 ; for ( int i
= head
[ x
] ; i
; i
= edge
[ i
] . next
) { int y
= edge
[ i
] . to
, v
= edge
[ i
] . v
; if ( dis
[ z
] [ y
] > dis
[ z
] [ x
] + v
) { dis
[ z
] [ y
] = dis
[ z
] [ x
] + v
; fro
[ r
] [ edge
[ i
] . to
] = x
; q
. push ( make_pair ( - dis
[ z
] [ y
] , y
) ) ; } } }
}
void output ( int x
, int y
) { while ( x
!= y
&& x
!= 0 ) { cout
<< x
<< ' ' ; x
= fro
[ 1 ] [ x
] ; } cout
<< x
; return ;
}
void output2 ( int x
, int y
) { if ( x
== y
) { printf ( "%d" , y
) ; return ; } if ( fro
[ 0 ] [ y
] == 0 ) { printf ( "%d" , y
) ; return ; } if ( fro
[ 0 ] [ y
] == x
) { printf ( "%d %d" , x
, y
) ; return ; } else { output2 ( x
, fro
[ 0 ] [ y
] ) ; printf ( " %d" , y
) ; }
}
int main ( ) { int a
, b
, w
; int ti
= 0 ;
while ( scanf ( "%d %d %d" , & n
, & s
, & e
) != EOF ) { cin
>> m
; while ( m
-- ) { scanf ( "%d %d %d" , & a
, & b
, & w
) ; add ( a
, b
, w
) ; add ( b
, a
, w
) ; } dijkstra ( s
, 0 , 0 ) ; dijkstra ( e
, 1 , 1 ) ; int ansdis
= inf
; int st
= 0 , ste
= 0 ; cin
>> k
; int dis1
, dis2
; while ( k
-- ) { scanf ( "%d %d %d" , & a
, & b
, & w
) ; dis1
= dis
[ 0 ] [ a
] + dis
[ 1 ] [ b
] + w
; dis2
= dis
[ 0 ] [ b
] + dis
[ 1 ] [ a
] + w
; if ( ansdis
> dis1
) { ansdis
= dis1
; st
= a
; ste
= b
; } if ( ansdis
> dis2
) { ansdis
= dis2
; st
= b
; ste
= a
; } } if ( ti
> 0 ) cout
<< endl
; ti
++ ; if ( ansdis
> dis
[ 0 ] [ e
] ) { output ( s
, e
) ; cout
<< endl
; cout
<< "Ticket Not Used" << endl
; cout
<< dis
[ 0 ] [ e
] << endl
; } else { output2 ( s
, st
) ; cout
<< ' ' ; output ( ste
, e
) ; cout
<< endl
; cout
<< st
<< endl
; cout
<< ansdis
<< endl
; } for ( int i
= 0 ; i
< m
; i
++ ) { fro
[ 0 ] [ i
] = 0 ; fro
[ 1 ] [ i
] = 0 ; } memset ( head
, 0 , sizeof ( head
) ) ; tot
= 0 ;
}
}
總結(jié)
以上是生活随笔 為你收集整理的Week7 B - TT 的旅行日记 的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
如果覺(jué)得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
