最短路径 ：虽然做过很多次最短路的题，spfa，bellman，floyd都用过不少。但是题目强调的“顺序”又让我加深了对最短路的理解。
当然，主要还是练习下STL：
pair型：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<memory>
#include<queue>
using namespace std;
const int maxn=;
const int maxm=;
const int inf=1e9;
int dis[maxn],n,m,s,t;
int Laxt[maxm],Next[maxm],To[maxm],Len[maxm],cnt,in[maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int > > >q;
void add(int u,int v,int d)
{
Next[++cnt]=Laxt[u];
Laxt[u]=cnt;
To[cnt]=v;
Len[cnt]=d;
}
void spfa()
{
while(!q.empty()){
int u=q.top().second;q.pop();
in[u]=;
for(int i=Laxt[u];i;i=Next[i]){
int v=To[i];
if(dis[v]>dis[u]+Len[i]){
dis[v]=dis[u]+Len[i];
if(!in[v]) {
in[v]=;
q.push(make_pair(dis[v],v));
}
}
}
}
}
int main()
{
int i,j,k,u,v,d;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
add(u,v,d);
add(v,u,d);
}
for(i=;i<=n;i++) dis[i]=inf;
dis[s]=; in[s]=;
q.push(make_pair(,s));
spfa();
printf("%d\n",dis[t]);
return ;
}
struct型
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<memory>
#include<queue>
using namespace std;
const int maxn=;
const int maxm=;
const int inf=1e9;
int dis[maxn],n,m,s,t;
int Laxt[maxm],Next[maxm],To[maxm],Len[maxm],cnt,in[maxn];
struct pii
{
int dist;
int node;
pii(int a,int b):dist(a),node(b){}//赋值
bool friend operator <(pii a,pii b){//重载
return a.dist>b.dist;
}
};
priority_queue<pii>q;
void add(int u,int v,int d)
{
Next[++cnt]=Laxt[u];
Laxt[u]=cnt;
To[cnt]=v;
Len[cnt]=d;
}
void spfa()
{
while(!q.empty()){
int u=q.top().node;q.pop();
in[u]=;
for(int i=Laxt[u];i;i=Next[i]){
int v=To[i];
if(dis[v]>dis[u]+Len[i]){
dis[v]=dis[u]+Len[i];
if(!in[v]) {
in[v]=;
pii tmp(dis[v],v);
q.push(tmp);
}
}
}
}
}
int main()
{
int i,j,k,u,v,d;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=;i<=m;i++){
scanf("%d%d%d",&u,&v,&d);
add(u,v,d);
add(v,u,d);
}
for(i=;i<=n;i++) dis[i]=inf;
dis[s]=; in[s]=;
pii tmp(,s);
q.push(tmp);
spfa();
printf("%d\n",dis[t]);
return ;
}