P1339 热浪Heat Wave Dijkstra

https://www.luogu.org/problemnew/show/P1339

题目描述:

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

#include<bits/stdc++.h>
using namespace std;
#define maxc 7000
#define maxt 3000

int t,c,ts,te;

struct Edge{
	int next;
	int to;
	int w;
}e[2*maxc];
int head[maxt];
int ans=0;
void addEdge(int u,int v,int w){
	int p=head[u];
	while(p){
		if(e[p].to==v&&e[p].w<=w) return ;
		p=e[p].next;
	}
	
	e[++ans].to=v;
	e[ans].w=w;
	e[ans].next=head[u];
	head[u]=ans;
}
int vis[maxt];
int dist[maxt];
void Dijkstra(){
	priority_queue< pair<int,int> , vector< pair<int,int> > , greater< pair<int,int> > > q;
	for(int i=1;i<=t;i++) dist[i]=2000;
	dist[ts]=0;
	q.push(make_pair(0,ts));
	while(!q.empty()){
		int p=q.top().second;q.pop();
		if(vis[p]) continue;
		vis[p]=1;
		int s=head[p];
		while(s){
			if(vis[e[s].to]==0&&dist[e[s].to]>dist[p]+e[s].w){
			    dist[e[s].to]=dist[p]+e[s].w;
			    q.push(make_pair(dist[e[s].to],e[s].to));
			}
			s=e[s].next;
		}
	}
	
}
int main(){
	
	std::ios::sync_with_stdio(false);
	cin>>t>>c>>ts>>te;
	int u,v,w;
	for(int i=0;i<c;i++){
		cin>>u>>v>>w;
		addEdge(u,v,w);
		addEdge(v,u,w);
	}
	Dijkstra();
	cout<<dist[te]<<endl;
	return 0;
}