最短路模板题
题意简述：
-
从一个单词想起另一个单词可以看作从一个点走向另一个点 。
-
可以将想起的时间看作权值 。
-
从一个点走到另一个点的最小权值 。
-
因为两个单词不能互相想起,所以是单向边 。
-
单向边很明显是一个有向图 。
-
有向图走不到输出 "Roger" 。
解题思路：
-
由最小权值我们可以很自然的想到最短路。
-
由于本题没有负权值，以我们可以想到使用 Dijkstra 算法（一种基于贪心的算法。
-
如果不会 Dijkstra 算法请往下拉或左转 P4779 【模板】单源最短路径（标准版）。
-
将从一个单词想起另一个单词的最短时间时间看作从一个点到另一个的最短。
-
做完最短路后如果目标点仍是初值的话则代表走不到。
-
时间大约为
O(q \cdot n \log n) 。
注意事项：
-
因为每一条边的权值最大为 10 的 9 次方 ，所以建议使用
long long进行存储。 -
不能仅以一个原点跑最短路因为这样可能无法准确的判断一个点可否到达另一个点。
-
建议每次找题目给定的原点进行最短路。
-
最短路建议使用 堆优化 的，不然会超时 。
-
如果不会手打堆，可以使用 优先队列 。
代码奉上
#include <bits/stdc++.h>
#define int long long
//本蒟蒻的码风不太好看QWQ
//蒟蒻的第一篇题解，审核大大求过QWQ
//如果空格又少了审核大大请说一下是哪里（实在找不到了。。QWQ）
using namespace std ;
const int N = 1005 ;
int ans[N] ;
int qu,n,m,bh,zhi ;
string a,b ;
struct ww{
int id,w ;
bool operator < (const ww &A) const {return w > A.w;} //优先队列按权值由小到大排序
}o;
vector<ww>bian[N] ;
map<string ,int >p ;
priority_queue<ww>q ;
inline int read(){
register int x = 0 , f = 1 ;
register char ch = getchar() ;
while( ch < '0' || ch > '9' ){
if( ch == '-' )f = -1 ;
ch =getchar() ;
}
while( ch >= '0' && ch <= '9' )
x = ( x << 1 ) + ( x << 3 ) + ( ch ^ 48 ) ,
ch =getchar() ;
return x * f;
}//快读
inline void write(int x){
if( x < 0 )putchar('-'),x = -x ;
if( x > 9 )write(x/10) ;
putchar( x%10+'0' ) ;
}//快写
void find(){
while(!q.empty()){
ww now = q.top() ;//取队首
if(ans[now.id] != now.w){
q.pop() ;
continue ;//走过的排除
}
for(int i = 0 ; i < bian[now.id].size() ; i++ )
if(ans[now.id]+bian[now.id][i].w<ans[bian[now.id][i].id])
ans[bian[now.id][i].id] = ans[now.id]+bian[now.id][i].w ,
o.id = bian[now.id][i].id , o.w = ans[bian[now.id][i].id],
q.push(o) ;//添加新点
q.pop() ;//弹出队首
}
}
main(){
// freopen("alias.in","r",stdin) ;
// freopen("alias.out","w",stdout) ;
n = read() , m = read() ;
for(int i = 1 ; i <= m ; ++i ){
cin>>a>>b ,zhi = read() ;
if(p[a]==0)p[a] = ++bh ;
if(p[b]==0)p[b] = ++bh ;//为新的字符串上编号
o.id =p[b] , o.w = zhi ;
bian[p[a]].push_back(o) ;//存图
}
qu = read() ;
for(int i = 1 ; i <= qu ; i++ ){
memset(ans,0x3f,sizeof(ans)) ;//将初始答案赋值为无限大
cin>>a>>b ;
o.id = p[a],o.w = 0 ;//队列的原点
q.push(o) ;
ans[p[a]] = 0 ;
find() ;
if(ans[p[b]]>=4557430888798830399)printf("Roger\n") ;//初值为0x3f
else write(ans[p[b]]),printf("\n") ;
}
return 0 ;
}