首页 > 代码库 > hdu--2544--题如其名<最短路>--dij<priority_queue>||spfa<queue>

hdu--2544--题如其名<最短路>--dij<priority_queue>||spfa<queue>

这题 让我深刻地 感受到了 题如其名 =-= .........

一直以来都写spfa 这次 也顺便写了下 dij<链式前向星&&priority_queue> 代码太长了..

但是 要是思路清晰的话 写下去的感觉很爽的...

当然 我还是更加喜欢 spfa

关于 链式前向星 可以---传送--出产地学习

关于 spfa -- 我没找到特别出色的介绍<我也写过..> 这个不难 你可以随便去找一篇来学习

关于 dij -- 也是图论的入门重要算法 介绍它的博客实在太多了...  但是 使用优先队列版本的dij 没见过详细介绍的

但 既然都是优化了 你只要明白了 dij的算法思想 你就能看懂我下面的优先队列来优化的写法---自己写heap 效率更高 但我还不会=-=-----

 1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5  6 int cnt; 7 const int inf = 0x3f3f3f3f; 8 const int size = 10010; 9 struct graph10 {11     int to;12     int next;13     int dist;14 }edge[size];15 int head[size];16 bool vis[size/100+10];17 int dist[size/100+10];18 19 struct data20 {21     int id;22     int dist;23     data( int u , int v ):id(u),dist(v){};24     data(){};25     bool operator < (const data& p)const26     {27         return dist > p.dist;//如果返回true 证明新添加进来的元素的dist更小 放在顶端 所以这是小堆28     }29 };30 31 void init( int st )32 {33     cnt = 0;34     memset( head , -1 , sizeof(head) );35     memset( vis , false , sizeof(vis) );36     memset( dist , inf , sizeof(dist) );37     dist[st] = 0;38 }39 40 void add( int st , int end , int cost )41 {42     edge[cnt].to = end;43     edge[cnt].dist = cost;44     edge[cnt].next = head[st];45     head[st] = cnt++;46 }47 48 void dij( int st , int end )49 {50     priority_queue<data>q;51     q.push( data( st , dist[st] ) );52     while( !q.empty() )53     {54         data temp = q.top();55         q.pop();56         if( vis[ temp.id ] )57             continue;58         else59             vis[ temp.id ] = true;60         if( temp.id == end )61             return;62         for( int i = head[ temp.id ] ; ~i ; i = edge[i].next )63         {64             if( !vis[ edge[i].to ] && dist[ temp.id ] + edge[i].dist < dist[ edge[i].to] )65             {66                 dist[ edge[i].to ] = dist[ temp.id ] + edge[i].dist;67                 q.push( data( edge[i].to , dist[ edge[i].to ] ) );68             }69         }70     }71 }72 73 int main()74 {75     cin.sync_with_stdio(false);76     int n , m , st , end , cost;77     while( cin >> n >> m &&(n||m) )78     {79         init( 1 );80         while( m-- )81         {82             cin >> st >> end >> cost;83             add( st , end , cost );84             add( end , st , cost );85         }86         dij( 1 , n );87         cout << dist[n] << endl;88     }89     return 0;90 }
View Code

 

 1 #include <iostream> 2 #include <cstring> 3 #include <queue> 4 using namespace std; 5  6 int n; 7 const int inf = 0x3f3f3f3f; 8 const int size = 110; 9 struct graph10 {11     int num;12     int next[size*10];13     int dist[size*10];14 }node[size];15 bool vis[size];16 int dist[size];17 18 void init( )19 {20     for( int i = 0 ; i<size ; i++ )21     {22         node[i].num = 0;23     }24     memset( vis , false , sizeof(vis) );25 }26 27 void spfa( )28 {29     queue<int>q;30     while( !q.empty() )31         q.pop();32     q.push(1);33     vis[1] = true;34     for( int i = 0 ; i<=n ; i++ )35     {36         dist[i] = i==1 ? 0 : inf;37     }38     while( !q.empty() )39     {40         int now = q.front();41         q.pop();42         vis[now] = false;43         for( int i = 0 ; i<node[now].num ; i++ )44         {45             if( dist[now] + node[now].dist[i] < dist[ node[now].next[i] ] )46             {47                 dist[ node[now].next[i] ] = dist[now] + node[now].dist[i];48                 if( !vis[ node[now].next[i] ] )49                 {50                     vis[ node[now].next[i] ] = true;51                     q.push( node[now].next[i] );52                 }53             }54         }55     }56 }57 58 int main()59 {60     int m , st , end , cost;61     while( cin >> n >> m &&(n||m) )62     {63         init( );64         while( m-- )65         {66             cin >> st >> end >> cost;67             node[st].next[ node[st].num ] = end;68             node[st].dist[ node[st].num++ ] = cost;69             node[end].next[ node[end].num ] = st;70             node[end].dist[ node[end].num++ ] = cost;71         }72         spfa( );73         cout << dist[n] << endl;74     }75     return 0;76 }
View Code


虽说 spfa 不稳定 可能会出现故意数据来卡它 ... 有必要这么 丧病吗#78....

这2个 完全可以当做模板吧...  只要你会了思想 就能自己手写出来了 到时候 也就自然而然会形成自己的风格-.-

 

today:

  这是最好的时代              这是最坏的时代

  这是智慧的时代              这是愚蠢的时代

  这是信仰的时期           这是怀疑的时期

  这是光明的季节       这是黑暗的季节

  这是希望之春          这是失望之冬

  人们面前有着各样事物  人们面前一无所有

  人们正在直登天堂    人们正在直下地狱

  ---------------------------------------------------------now?