y总用的spfa
我用的Dijkstra+堆优化
岂不比spfa快
//来自算法提高课
#include<bits/stdc++.h>
using namespace std;
const int N = 13000;
int n,m,ts,te,dist[N];
int cnt,first[N];
bool r[N];
struct edge{
int end,len,nxt;
}bian[N];
void addedge(int s,int e,int w){
cnt++;
bian[cnt].end = e;
bian[cnt].len = w;
bian[cnt].nxt = first[s];
first[s] = cnt;
}
priority_queue<pair<int,int> > h;
void dijkstra(int s){
dist[s] = 0;
for(int i=1; i<=n; i++) h.push(make_pair(-dist[i],i));
for(int i=1; i<=n; i++){
while(r[h.top().second]) h.pop();
pair<int,int> top = h.top();
h.pop();
int d = -top.first;
int p = top.second;
r[p] = true;
for(int x=first[p]; x!=0; x=bian[x].nxt){
int end = bian[x].end;
int len = bian[x].len;
int newd = dist[p]+len;
if(newd<dist[end]){
dist[end] = newd;
h.push(make_pair(-dist[end],end));
}
}
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&ts,&te);
for(int i=1; i<=n; i++) dist[i]=2147483647;
for(int i=1; i<=m; i++){
int s,e,w;
scanf("%d%d%d",&s,&e,&w);
addedge(s,e,w), addedge(e,s,w);
}
dijkstra(ts);
printf("%d\n",dist[te]);
return 0;
}
秀儿。。。
这难道不是常规操作吗(联赛卡过spfa)
就是说话的语气有点骚【笑】
算法没问题
笑)