第二个点玄学WA掉,不准下数据,很悲伤/kk
有没有dalao帮忙看一看啊 orz
奉上蒟蒻丑陋的代码(Dijkstra跑的最短路):
#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<int,int> > q;
int n,m,t,b,E,x,y,z;
int tot,dis[1000010],vis[1000010],head[1000010];
struct node {
int to,net,val;
} e[1000010];
struct nodes {
int t,p;
} a[1000010];
inline void add(int u,int v,int w) {
e[++tot].to=v;
e[tot].val=w;
e[tot].net=head[u];
head[u]=tot;
}
inline void dijkstra(int s) {
for(register int i=1;i<=n;i++) {
vis[i]=0;
dis[i]=20050206;
}
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty()) {
int x=q.top().second;
q.pop();
if(vis[x]) continue;
vis[x]=1;
for(register int i=head[x];i;i=e[i].net) {
int v=e[i].to;
if(dis[v]>dis[x]+e[i].val) {
dis[v]=dis[x]+e[i].val;
q.push(make_pair(-dis[v],v));
}
}
}
}
inline bool cmp(nodes x,nodes y) {
return x.t<y.t;
}
int main() {
scanf("%d%d%d%d",&n,&m,&b,&E);
for(register int i=1;i<=m;i++) {
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
scanf("%d",&t);
for(register int i=1;i<=t;i++) {
scanf("%d%d",&a[i].t,&a[i].p);
}
sort(a+1,a+1+t,cmp);
dijkstra(b);
if(dis[E]<a[1].t||t==0) {
printf("%d",dis[E]);
return 0;
}
for(register int i=1;i<=t;i++) {
if(dis[a[i].p]<=a[i].t) {
printf("%d",a[i].t);
return 0;
}
}
return 0;
}