acwing1129. 热浪

题目

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！

他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。

农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。

这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。

除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。

每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含 C 条直接连接 2 个城镇的道路。

每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。

求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。

题解

单源最短路问题，由于顶点和边数较多（6200边，2500顶点），需要用到优先队列来优化。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
typedef pair<int,int>PII;
const int N=13000;
int h[N],e[N],ne[N],w[N],idx;
int n,m,start,target;
int dist[2500];
bool st[N];
int dijkstra(){
    memset(dist,0x3f,sizeof dist);
    dist[start]=0;
    priority_queue<PII,vector<PII>,greater<PII>>heap;
    heap.push({0,start});
    while(heap.size()){
        auto t=heap.top();
        heap.pop();
        int vec=t.second;
        if(st[vec])continue;
        st[vec]=true;
        for(int i=h[vec];i!=-1;i=ne[i]){
            int j=e[i];
            if(dist[j]>w[i]+dist[vec]){//更新距离
                dist[j]=w[i]+dist[vec];
                heap.push({dist[j],j});
            }
        }
    }
    if(dist[target]==0x3f3f3f3f)return -1;
    return dist[target];
}
void add(int a,int b,int c){
    w[idx]=c;
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
    
}
int main(){
    cin>>n>>m>>start>>target;
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    cout<<dijkstra()<<endl;
    
    return 0;
}