题面:
题意:
给定一张无向图和起点、终点。
每条边有一个权值为通过这条边所需要的时间。
每个点有一个字符 LMR,其中 L表示在这一点只能处于 L状态, R表示在这一点只能处于 R状态, M表示在这一点可以处于 L状态,也可以处于 R状态。状态的切换需要一个时间 x,状态的切换可以在路程过程中进行,但是切换状态时,必须停下来。
题解:
dijkstra 即可,其中 d[x][k]表示到达 x 点且处于状态 k 的最短路。
代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#include<list>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
//#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=1e9+7;
const double eps=1e-5;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxp=1100;
const int maxm=400100;
const int up=1000;
const int N=26;
int head[maxn],ver[maxm],nt[maxm],tot;
ll d[maxn][2],edge[maxm];
bool ha[maxn][2];
char str[maxn];
int n,m,s,t;
ll time;
struct node
{
int x,sh;
ll val;
node(){}
node(int a,int b,ll c)
{
x=a,sh=b,val=c;
}
friend bool operator<(const node &a,const node &b)
{
return a.val>b.val;
}
};
void add(int x,int y,ll z)
{
ver[++tot]=y,edge[tot]=z;
nt[tot]=head[x],head[x]=tot;
}
void init(int n)
{
for(int i=1;i<=n;i++)
head[i]=0;
tot=1;
}
ll dij(int s,int t)
{
for(int i=1;i<=n;i++)
{
d[i][0]=d[i][1]=lnf;
ha[i][0]=ha[i][1]=false;
}
priority_queue<node>q;
if(str[s]=='L') q.push(node(s,0,0)),d[s][0]=0;
if(str[s]=='R') q.push(node(s,1,0)),d[s][1]=0;
if(str[s]=='M')
{
q.push(node(s,0,0)),d[s][0]=0;
q.push(node(s,1,0)),d[s][1]=0;
}
while(q.size())
{
int x=q.top().x;
int sh=q.top().sh;
q.pop();
if(ha[x][sh]) continue;
ha[x][sh]=true;
for(int i=head[x];i;i=nt[i])
{
int y=ver[i];
ll z=edge[i];
if(str[y]=='L')
{
if(sh==0)
{
if(d[y][0]>d[x][0]+z)
{
d[y][0]=d[x][0]+z;
q.push(node(y,0,d[y][0]));
}
}
else if(sh==1)
{
if(d[y][0]>d[x][1]+z+time)
{
d[y][0]=d[x][1]+z+time;
q.push(node(y,0,d[y][0]));
}
}
}
else if(str[y]=='R')
{
if(sh==0)
{
if(d[y][1]>d[x][0]+z+time)
{
d[y][1]=d[x][0]+z+time;
q.push(node(y,1,d[y][1]));
}
}
else if(sh==1)
{
if(d[y][1]>d[x][1]+z)
{
d[y][1]=d[x][1]+z;
q.push(node(y,1,d[y][1]));
}
}
}
else if(str[y]=='M')
{
if(sh==0)
{
if(d[y][0]>d[x][0]+z)
{
d[y][0]=d[x][0]+z;
q.push(node(y,0,d[y][0]));
}
if(d[y][1]>d[x][0]+z+time)
{
d[y][1]=d[x][0]+z+time;
q.push(node(y,1,d[y][1]));
}
}
else if(sh==1)
{
if(d[y][0]>d[x][1]+z+time)
{
d[y][0]=d[x][1]+z+time;
q.push(node(y,0,d[y][0]));
}
if(d[y][1]>d[x][1]+z)
{
d[y][1]=d[x][1]+z;
q.push(node(y,1,d[y][1]));
}
}
}
}
}
if(str[t]=='L') return d[t][0];
else if(str[t]=='R') return d[t][1];
else return min(d[t][0],d[t][1]);
}
int main(void)
{
int tt;
scanf("%d",&tt);
while(tt--)
{
int x,y;
ll z;
scanf("%d%d%d%d%lld",&n,&m,&s,&t,&time);
init(n);
scanf("%s",str+1);
for(int i=1;i<=m;i++)
{
scanf("%d%d%lld",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
printf("%lld\n",dij(s,t));
}
return 0;
}