题解 | #[USACO 2009 Oct G]Heat Wave#

思路

这道题很开放，spfa能过、Dijkstra能过，普通求法（见代码）也能过。
这边供上一个Dijkstra堆优化板子求最短路。
坑点：注意优先队列默认是从大到小的，重载运算符要写a.dis>b.dis，别把堆优化做成堆劣化。

Dijkstral代码

#include<bits/stdc++.h>
#define int ll
using namespace std;
typedef long long ll;
const int maxn=2505,maxm=6000000;

struct E{
    int to,dis;
};
bool operator <(const E a,const E b){
    return a.dis>b.dis;
}

vector<E>G[maxn];
priority_queue<E>q;
int n,m,s,t,u,v,w,dis[2505];

signed main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=0;i<=n;i++) dis[i]=1e9+7;
    dis[s]=0;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back((E){v,w});
        G[v].push_back((E){u,w});
    }
    q.push((E){s,0});
    while(!q.empty()){
        E fro=q.top();
        q.pop();
        for(int i=0;i<G[fro.to].size();i++){
            int to=G[fro.to][i].to,d=G[fro.to][i].dis;
            if(dis[fro.to]+d<dis[to]){
                dis[to]=dis[fro.to]+d;
                q.push((E){to,dis[to]});
            }    
        }
    }
    cout<<dis[t];
    return 0;
}

普通做法

#include<bits/stdc++.h>
using namespace std;

int n,m,s,t,mp[2501][2501]={0},vis[2501];
queue<int>q;
inline void read(int &data){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    data=x;
}

int main(){
    int a,b,v;
    read(n);read(m);read(s);read(t);
    for(int i=1;i<=m;i++){
        read(a);read(b);read(v);
        mp[a][b]=mp[b][a]=v;
    } 
    for(int i=1;i<=n;i++) vis[i]=0xffff;
    vis[s]=0;
    q.push(s);
    while(!q.empty()){
        int now=q.front();q.pop();
        for(int i=1;i<=n;i++){
            if(mp[now][i]&&mp[now][i]+vis[now]<vis[i]){
                vis[i]=mp[now][i]+vis[now];
                q.push(i);
            } 
        }
    } 
    printf("%d",vis[t]);
    return 0;
}