多多色-多人伦交性欧美在线观看-多人伦精品一区二区三区视频-多色视频-免费黄色视屏网站-免费黄色在线

國內(nèi)最全I(xiàn)T社區(qū)平臺(tái) 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁 > 互聯(lián)網(wǎng) > POJ 3653 & ZOJ 2935 & HDU 2722 Here We Go(relians) Again(最短路dijstra)

POJ 3653 & ZOJ 2935 & HDU 2722 Here We Go(relians) Again(最短路dijstra)

來源:程序員人生   發(fā)布時(shí)間:2014-11-14 08:31:40 閱讀次數(shù):1832次
題目鏈接:

PKU:http://poj.org/problem?id=3653

ZJU:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1934

HDU:http://acm.hdu.edu.cn/showproblem.php?pid=2722


Description

The Gorelians are a warlike race that travel the universe conquering new worlds as a form of recreation. Given their violent, fun-loving nature, keeping their leaders alive is of serious concern. Part of the Gorelian security plan involves changing the traffic patterns of their cities on a daily basis, and routing all Gorelian Government Officials to the Government Building by the fastest possible route.

Fortunately for the Gorelian Minister of Traffic (that would be you), all Gorelian cities are laid out as a rectangular grid of blocks, where each block is a square measuring 2520 rels per side (a rel is the Gorelian Official Unit of Distance). The speed limit between two adjacent intersections is always constant, and may range from 1 to 9 rels per blip (a blip, of course, being the Gorelian Official Unit of Time). Since Gorelians have outlawed decimal numbers as unholy (hey, if you're the dominant force in the known universe, you can outlaw whatever you want), speed limits are always integer values. This explains why Gorelian blocks are precisely 2520 rels in length: 2520 is the least common multiple of the integers 1 through 9. Thus, the time required to travel between two adjacent intersections is always an integer number of blips.

In all Gorelian cities, Government Housing is always at the northwest corner of the city, while the Government Building is always at the southeast corner. Streets between intersections might be one-way or two-way, or possibly even closed for repair (all this tinkering with traffic patterns causes a lot of accidents). Your job, given the details of speed limits, street directions, and street closures for a Gorelian city, is to determine the fastest route from Government Housing to the Government Building. (It is possible, due to street directions and closures, that no route exists, in which case a Gorelian Official Temporary Holiday is declared, and the Gorelian Officials take the day off.)

Gorelian city

The picture above shows a Gorelian City marked with speed limits, one way streets, and one closed street. It is assumed that streets are always traveled at the exact posted speed limit, and that turning a corner takes zero time. Under these conditions, you should be able to determine that the fastest route from Government Housing to the Government Building in this city is 1715 blips. And if the next day, the only change is that the closed road is opened to two way traffic at 9 rels per blip, the fastest route becomes 1295 blips. On the other hand, suppose the three one-way streets are switched from southbound to northbound (with the closed road remaining closed). In that case, no route would be possible and the day would be declared a holiday.

Input

The input consists of a set of cities for which you must find a fastest route if one exists. The first line of an input case contains two integers, which are the vertical and horizontal number of city blocks, respectively. The smallest city is a single block, or 1 by 1, and the largest city is 20 by 20 blocks. The remainder of the input specifies speed limits and traffic directions for streets between intersections, one row of street segments at a time. The first line of the input (after the dimensions line) contains the data for the northernmost east-west street segments. The next line contains the data for the northernmost row of north-south street segments. Then the next row of east-west streets, then north-south streets, and so on, until the southernmost row of east-west streets. Speed limits and directions of travel are specified in order from west to east, and each consists of an integer from 0 to 9 indicating speed limit, and a symbol indicating which direction traffic may flow. A zero speed limit means the road is closed. All digits and symbols are delimited by a single space. For east-west streets, the symbol will be an asterisk '*' which indicates travel is allowed in both directions, a less-than symbol '<' which indicates travel is allowed only in an east-to-west direction, or a greater-than symbol '>' which indicates travel is allowed only in a west-to-east direction. For north-south streets, an asterisk again indicates travel is allowed in either direction, a lowercase "vee" character 'v' indicates travel is allowed only in a north-to-south directions, and a caret symbol '^' indicates travel is allowed only in a south-to-north direction. A zero speed, indicating a closed road, is always followed by an asterisk. Input cities continue in this manner until a value of zero is specified for both the vertical and horizontal dimensions.

Output

For each input scenario, output a line specifying the integer number of blips of the shortest route, a space, and then the word "blips". For scenarios which have no route, output a line with the word "Holiday".

Sample Input

2 2 9 * 9 * 6 v 0 * 8 v 3 * 7 * 3 * 6 v 3 * 4 * 8 * 2 2 9 * 9 * 6 v 9 * 8 v 3 * 7 * 3 * 6 v 3 * 4 * 8 * 2 2 9 * 9 * 6 ^ 0 * 8 ^ 3 * 7 * 3 * 6 ^ 3 * 4 * 8 * 0 0

Sample Output

1715 blips 1295 blips Holiday

Source

Mid-Central USA 2007


PS:

題意比較惡心,輸入更惡心,還要分東南西北4個(gè)方向!

處理1下輸入,在隨意用1個(gè)最短路就行了!


代碼以下:

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define INF 0x3f3f3f3f const int maxn = 547; int mapp[maxn][maxn]; int dijkstra(int start,int n) { int dis[maxn]; int mark[maxn]; int k, min; memset(mark,0,sizeof(mark)); for(int i = 1; i <= n; i++) dis[i] = INF; dis[start] = 0; for(int i = 1; i <= n; i++) { min = INF; for(int j = 1; j <= n; j++) { if(!mark[j] && dis[j]<min) { min=dis[j]; k=j; } } mark[k] = 1; for(int j = 1; j <= n; j++) { if(mapp[k][j]!=0) { if(dis[j] > dis[k]+mapp[k][j]) dis[j] = dis[k]+mapp[k][j]; } } } return dis[n]; } int main() { int v, h, w; char dir; while(~scanf("%d%d",&v,&h)) { if(v==0 && h==0) break; memset(mapp,0,sizeof(mapp)); int a, b; for(int i = 0; i <= v; i++) { for(int j = 1; j <= h; j++) { scanf("%d %c",&w,&dir); if(w == 0) continue; a = i*(h+1)+j; b = a+1; int ti = 2520/w; if(dir == '*') mapp[a][b] = mapp[b][a] = ti; else if(dir == '>') mapp[a][b] = ti; else mapp[b][a] = ti; } if(i!=v)//不是最后1行 { for(int j = 1; j <= h+1; j++)//多1個(gè) { scanf("%d %c",&w,&dir); if(w == 0) continue; a = i*(h+1)+j; b = a+h+1; int ti = 2520/w; if(dir == '*') mapp[a][b] = mapp[b][a] = ti; else if(dir == 'v') mapp[a][b] = ti; else mapp[b][a] = ti; } } } int tt = (v+1)*(h+1); int ans = dijkstra(1,tt); if(ans != INF) printf("%d blips ",ans); else printf("Holiday "); } return 0; }


生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 亚洲成人看片 | 国产高清看片日韩欧美久久 | 日本一二线不卡在线观看 | 国产成人不卡亚洲精品91 | 亚洲网站色 | 婷婷激情五月 | 国产精品嫩草影院88v | 亚洲一区二区三区精品国产 | 亚洲欧美日韩国产精品 | 亚洲欧美国产另类视频 | 在线观看日本一区 | 日韩精品久久不卡中文字幕 | 亚洲精品资源在线 | 精品欧美视频 | 一级特黄aa大片免费播放视频 | 亚洲福利视频一区 | 尤物在线视频观看 | 性做久久久久免费观看 | 亚洲伊人久久大香线蕉苏妲己 | 韩国片在线观看 | 亚洲日韩色图 | 欧美a在线播放 | 青青综合 | 国产xxxxfreexxxxxvideo| 24小时免费观看www日本 | 老司机午夜精品视频播放 | 欧美一级毛片高清视频 | 亚洲精品视频免费 | 亚洲国产欧美在线人成 | 久久精品国产99久久99久久久 | 久久久精品成人免费看 | 亚洲国产日韩欧美高清片a 亚洲国产日韩欧美一区二区三区 | 手机福利在线观看 | 亚洲图片在线 | 国产一区自拍视频 | 欧美精品第一页 | 中文字幕精品一区二区精品 | youjizz久久| 精品一区二区三区 不卡高清 | 亚洲精品欧美精品中文字幕 | 最新毛片久热97免费精品视频 |