[洛谷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)最小的总费用。

输入格式：

第一行: 4个由空格隔开的整数: T, C, Ts, Te,第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci

输出格式：

一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

输入样例：

7 11 5 4

2 4 2

1 4 3

7 2 2

3 4 3

5 7 5

7 3 3

6 1 1

6 3 4

2 4 3

5 6 3

7 2 1

输出样例：

7

题解：单源最短路问题，可以用spfa或者dijkstra快速解决。（图论还是挺擅长的。）

单源最短路算法spfa或者dijkstra可以快速的找出从一个点到达所有点的最短路径。dijkstra可以使用优先队列进行时间优化，从O(n^2)

优化到O(nlogn)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
#define LiangJiaJun main
#define INF 2000000004
#define pa pair<int,int>
using namespace std;
priority_queue<pa,vector<pa>,greater<pa> >q;
int h[],t,c,ts,te,ne=,dis[];
bool vis[];
struct edge{
    int to,next,w;
}e[];
void insert(int u,int v,int w){
     e[++ne].to = v;
     e[ne].next = h[u];
     e[ne].w = w;
     h[u] = ne;
}
int dijkstra(int st,int ed){
    memset(dis,/,sizeof(dis));
    dis[st]=;
    q.push(make_pair(,st));
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x])continue;
        vis[x] = ;
        for(int i=h[x];i;i=e[i].next){
            if(dis[e[i].to]>dis[x]+e[i].w){
               dis[e[i].to]=dis[x]+e[i].w;
               q.push(make_pair(dis[e[i].to],e[i].to));
            }
        }
    }
    return dis[ed];
}
int LiangJiaJun(){
    scanf("%d%d%d%d",&t,&c,&ts,&te);
    for(int i=;i<=c;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        insert(u,v,w);insert(v,u,w);
    }
    printf("%d\n",dijkstra(ts,te));
    return ;
}