「2018-12-02模拟赛」T1|「2018-12-02模拟赛」T1 最短路解题报告「2018-12-02模拟赛」T1最短路解

1.最短路(short.pas/cpp/in/out) 问题描述：小 C 终于被小 X 感动了，于是决定与他看电影，然而小 X 距离电影院非常远，现在假设
每条道路需要花费小 X 的时间为 1，由于有数以万计的好朋友沿路祝贺，导致小 X 在通过某
些路不得不耗费 1 的时间来和他们聊天，尽管他希望尽早见到小 C，所以他希望找到一条最
快时间到达电影院的路。
一开始小 X 在 1 号点，共有 N 个点，M 条路，电影院为 T 号点。
输入：第一行 3 个正整数，分别为 n，m 和 t。
以下 m 行，每行 3 个数，表示连接的编号以及权值。
（注意，可能会有重边）
输出：一行一个数，表示 1 到 t 的最短路。
样例输入：

10 12 6 3 9 2 6 9 2 6 2 1 3 1 1 1 9 2 2 8 2 7 10 1 7 2 1 10 0 1 8 1 1 1 5 2 3 7 2

样例输出：

4

数据范围：对于 30%的数据：n<=10，m<=20；
对于 60%的数据：n<=1 000，m<=20 000；
对于 100%的数据：n<=5 000 000，m<=10 000 000。
时空限制 【「2018-12-02模拟赛」T1|「2018-12-02模拟赛」T1 最短路解题报告】注意下这道题时间限制:\(2.5ms\) 空间限制:\(1024MB\) 好大呀
思路把因为边权只有可能是1和2，所以我们可以把边权为2的点拆成两条边，然后广搜~
最大的测试点还是达到了1.3+s QAQ 无能为力嘤嘤嘤~
代码

#include using namespace std; #define MAXN 10000005 #define MAXM 20000005 #define INF 0x7f7f7f7fint N, M, T; int hd[MAXN], to[MAXM << 1], nxt[MAXM << 1], tot, dis[MAXN]; int Q[MAXN], ph(1), pt(0); int x, y, z; char B[150<<20], *S = B; int read(){ int ans(0); while( !isdigit(*S) ) S++; while( isdigit(*S) ) ans = ans * 10 + ( (*S) ^ '0' ), S++; return ans; }void Add( int x, int y ){ nxt[++tot] = hd[x]; to[tot] = y; hd[x] = tot; nxt[++tot] = hd[y]; to[tot] = x; hd[y] = tot; }int main(){ freopen( "short.in", "r", stdin ); freopen( "short.out", "w", stdout ); fread( B, 1, 150 << 20, stdin ); N = read(); M = read(); T = read(); for ( int i = 1; i <= M; ++i ){ x = read(); y = read(); z = read(); if ( z & 1 ) Add( x, y ); else Add( x, ++N ), Add( y, N ); } Q[++pt] = 1; memset( dis, -1, sizeof dis ); dis[1] = 0; while( pt >= ph ){ int t(Q[ph++]); for ( int i = hd[t]; i; i = nxt[i] ) if ( dis[to[i]] < 0 ){ dis[to[i]] = dis[t] + 1, Q[++pt] = to[i]; if ( t == T ) break; } } printf( "%d\n", dis[T] ); return 0; }

转载于:https://www.cnblogs.com/louhancheng/p/10055025.html