spfa邻接表版本

热浪洛谷oj1339

题目描述 Description

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。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)最小的总费用。

 输入输出格式 Input/output

输入格式： 第一行: 4个由空格隔开的整数: T, C, Ts, Te
第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci 输出格式： 一个单独的整数表示从Ts到Te的最小总费用。数据保证至少存在一条道路。

 输入输出样例 Sample input/output

样例测试点#1

输入样例： 在线IDE 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

 说明 description

【样例说明】
5->6->1->4 (3 + 1 + 3)

spfa

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define adde(u,v,d) add(u,v,d),add(v,u,d)
const int nmax=2510;
const int maxn=6205<<1;
const int inf=0x3f3f3f3f;
struct edge{
  int to,dist;
  edge*next;
};
edge edges[maxn],*pt,*head[nmax];
int d[nmax],v[nmax];
void add(int u,int v,int d){
   pt->to=v;
   pt->dist=d;
   pt->next=head[u];
   head[u]=pt++;
}
int main(){
   int n,m,i,j,k,l,s,t;
   cin>>n>>m>>s>>t;
   pt=edges;
   clr(head,0);
   rep(i,m){
     cin>>j>>k>>l;
     adde(j,k,l);
   }
   queue<int>q;
   q.push(s);
   clr(v,0);
   rep(i,n+1) d[i]=inf;
   v[s]=0;
   d[s]=0;
   while(!q.empty()){
      int u=q.front();
      q.pop();
      v[u]=0;
      for(edge*o=head[u];o;o=o->next){
         int to=o->to;int di=o->dist;
         if(d[to]>d[u]+di){
           d[to]=d[u]+di;
           if(!v[to]){
             q.push(to);
             v[to]=1;
           }
         }
      }
   }
   cout<<d[t]<<endl;
   return 0;
}

dijkstra

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define clr(x,c) memset(x,c,sizeof(x))
#define adde(u,v,d) add(u,v,d),add(v,u,d)
const int nmax=2505;
const int maxn=6205<<1;
const int inf=0x3f3f3f3f;
struct edge{
  int to,dist;
  edge *next;
};
edge*head[nmax],*pt,edges[nmax];
int d[nmax];
void add(int u,int v,int d){
  pt->to=v;
  pt->dist=d;
  pt->next=head[u];
  head[u]=pt++;
}
struct node{
  int x,d;
  bool operator<(const node&rhs)const{
   return d>rhs.d;}
};
int main(){
   int n,m,i,j,k,l,s,t;
   cin>>n>>m>>s>>t;

  ！！！！！！！！！pt=edges;！！！！！不用v数组来记录！！！和spfa的两个不同之处！！！！！
   clr(head,0);
   rep(i,m){
     cin>>j>>k>>l;
     adde(j,k,l);
   }
   rep(i,n+1) d[i]=inf;
   d[s]=0;
   priority_queue<node>q;
   q.push((node){s,0});
   while(!q.empty())
   {
     int x=q.top().x;
  int di=q.top().d;
  q.pop();
     for(edge* o=head[x];o;o=o->next){
       int to=o->to;
       int dist=o->dist;
       if(d[to]>di+dist){
         d[to]=di+dist;
         q.push((node){to,d[to]});
       }
     }
   }
   cout<<d[t]<<endl;
   return 0;
}