洛谷P1339 [USACO09OCT]热浪Heat Wave 简单最短路
思路：
这道题的n较小，直接用dijkstra即可。
代码如下：
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<string>
#include<vector>
#define MAX 2505
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;int n,m,s,t;
int mp[MAX][MAX],dis[MAX],visit[MAX];void dijkstra(int s){dis[s]=0;for(int i=0;i<=n;i++){int u=-1,minl=INF;for(int j=1;j<=n;j++){if(dis[j]<minl&&visit[j]==0){u=j;minl=dis[j];}}if(u==-1) return;visit[u]=1;for(int v=1;v<=n;v++){if(visit[v]==0&&mp[u][v]!=INF){if(dis[v]>dis[u]+mp[u][v]){dis[v]=dis[u]+mp[u][v];}}}}
}int main(){for(int i=0;i<MAX;i++){//初始化mpfor(int j=0;j<MAX;j++){mp[i][j]=INF;}}for(int i=0;i<MAX;i++){//初始化visit和disvisit[i]=0;dis[i]=INF;}scanf("%d%d%d%d",&n,&m,&s,&t);int a,b,len;for(int i=0;i<m;i++){//读入数据scanf("%d%d%d",&a,&b,&len);mp[a][b]=mp[b][a]=len;}dijkstra(s);printf("%d",dis[t]);return 0;
}