如果你只得了10pts，请双向建边！请双向建边！！请双向建边！！！

修改前：

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,head[2525],d[2525],tot,x,y,z;
bool vis[2525];
struct node{
  int u,v,w,nxt;
}e[6262];
void add(int u,int v,int w){
  e[++tot].u=u;
  e[tot].v=v;
  e[tot].w=w;
  e[tot].nxt=head[u];
  head[u]=tot;
}
priority_queue<pair<int,int> >q;
int main(){
  scanf("%d%d%d%d",&n,&m,&s,&t);
  memset(d,0x3f,sizeof(d));
  for(int i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z);
  }
  d[s]=0;
  q.push(make_pair(-d[s],s));
  while(!q.empty()){
    pair<int,int>tmp=q.top();
    q.pop();
    x=tmp.second;
    if(vis[x])continue;
    vis[x]=true;
    for(int i=head[x];i;i=e[i].nxt){
      y=e[i].v;
      if(d[y]>e[i].w+d[x]){
        d[y]=e[i].w+d[x];
        q.push(make_pair(-d[y],y));
      }
    }
  }
  printf("%d\n",d[t]);
  return 0;
}

记录详情

修改后：

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,head[2525],d[2525],tot,x,y,z;
bool vis[2525];
struct node{
  int u,v,w,nxt;
}e[6262*2];
void add(int u,int v,int w){
  e[++tot].u=u;
  e[tot].v=v;
  e[tot].w=w;
  e[tot].nxt=head[u];
  head[u]=tot;
}
priority_queue<pair<int,int> >q;
int main(){
  scanf("%d%d%d%d",&n,&m,&s,&t);
  memset(d,0x3f,sizeof(d));
  for(int i=1;i<=m;i++){
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z);
    add(y,x,z);
  }
  d[s]=0;
  q.push(make_pair(-d[s],s));
  while(!q.empty()){
    pair<int,int>tmp=q.top();
    q.pop();
    x=tmp.second;
    if(vis[x])continue;
    vis[x]=true;
    for(int i=head[x];i;i=e[i].nxt){
      y=e[i].v;
      if(d[y]>e[i].w+d[x]){
        d[y]=e[i].w+d[x];
        q.push(make_pair(-d[y],y));
      }
    }
  }
  printf("%d\n",d[t]);
  return 0;
}

记录详情