这么naive的题面一看就是最短路模板题~~~
ok。首先是floyd算法，tts，记得把k放在最外面就行了。
1 #include2 #include 3 #include 4 using namespace std; 5 int a[2501][2501]; 6 int main() 7 { 8 int m,n,c,b; 9 memset(a,0x3f,sizeof(a));10 scanf ("%d%d%d%d",&n,&m,&c,&b);11 int x,y,z;12 while(m--)13 {14 scanf ("%d%d%d",&x,&y,&z);15 a[x][y]=z;16 a[y][x]=z;17 }18 for(int k=1;k<=n;k++)19 {20 for(int i=1;i<=n;i++)21 {22 for(int j=1;j<=n;j++)23 {24 a[i][j]=min(a[i][j],a[i][k]+a[k][j]);25 }26 }27 }28 printf("%d",a[c][b]);29 return 0;30 }
没有任何的参考价值，除非你要做多源最短路径(☺)
next,SPFA算法，最短路径更快算法(☺)，shortest path faster algorithm
思想是这样的：从起点开始入队，然后每次取出一个点，消除标记，轮边松弛。
对于松弛了的边，如果在队中就不用管。否则入队+标记。
然后就能很naive的输出答案了！
注意：当一个点进队超过n次就有负环。
十分规范的模板。
1 #include2 #include 3 using namespace std; 4 const int N = 1000010; 5 int n,top; 6 struct Edge 7 { 8 int u,v,len,next,num; 9 }edge[N];10 struct Point11 {12 int dis=0x3f3f3f3f,e,c,num;13 bool vis;14 }point[N];15 16 bool spfa(int k)17 {18 queue p;19 point[k].vis=1;20 point[k].c++;21 point[k].dis=0;22 p.push(k);23 int op,ed,i;24 while(!p.empty())25 {26 op=p.front();27 p.pop();28 point[op].vis=0;29 i=point[op].e;30 while(i)31 {32 ed=edge[i].v;33 if(point[ed].dis>point[op].dis+edge[i].len)34 {35 point[ed].dis=point[op].dis+edge[i].len;36 if(point[ed].vis) continue;37 point[ed].vis=1;38 p.push(ed);39 point[ed].c++;40 if(point[ed].c>n) return 0;41 }42 i=edge[i].next;43 }44 }45 return true;46 }47 void add(int x,int y,int z)48 {49 top++;50 edge[top].u=x;51 edge[top].v=y;52 edge[top].len=z;53 edge[top].num=top;54 edge[top].next=point[x].e;55 point[x].e=top;56 return;57 }58 int main()59 {60 int m,a,b;61 scanf ("%d%d%d%d",&n,&m,&a,&b);62 for(int i=1;i<=n;i++) point[i].num=i;63 int x,y,z;64 for(int i=1;i<=m;i++)65 {66 scanf ("%d%d%d",&x,&y,&z);67 add(x,y,z);68 add(y,x,z);69 }70 if(!spfa(a)) printf("-1");71 else printf("%d",point[b].dis);72 return 0;73 }
接下来是稠密图上的dijkstra算法，di jk s tra(☺)
思想：来个优先队列，dis小的点先出。
起点入队，然后每次取出一个未标记的点标记已读，然后轮边。
如果终点被标记就continue，记得更新i。否则松弛一下，不管有没有成功都入队。
今天刚打的代码，也很规范。
(缺点：边权不能为负)
1 #include2 #include 3 using namespace std; 4 const int N = 1000010; 5 int top; 6 struct Edge 7 { 8 int u,v,len,next,num; 9 }edge[N];10 struct Point11 {12 int e,dis=0x3f3f3f3f,c,num;13 bool vis;14 bool operator < (const Point &a) const15 {16 return this->dis > a.dis;17 }18 }point[N];19 20 void dijkstra(int k)21 {22 priority_queue p;23 p.push(point[k]);24 point[k].vis=1;25 point[k].dis=0;26 int op,ed,i;27 while(!p.empty())28 {29 while((!p.empty())&&(p.top().vis)) p.pop();30 if(p.empty()) break;31 op=p.top().num;32 p.pop();33 point[op].vis=1;34 i=point[op].e;35 while(i)36 {37 ed=edge[i].v;38 if(point[ed].vis) {i=edge[i].next;continue;}39 if(point[ed].dis>point[op].dis+edge[i].len) point[ed].dis=point[op].dis+edge[i].len;40 p.push(point[ed]);41 i=edge[i].next;42 }43 }44 return;45 }46 47 48 void add(int x,int y,int z)49 {50 top++;51 edge[top].u=x;52 edge[top].v=y;53 edge[top].len=z;54 edge[top].num=top;55 edge[top].next=point[x].e;56 point[x].e=top;57 return;58 }59 int main()60 {61 int m,n,a,b;62 scanf ("%d%d%d%d",&n,&m,&a,&b);63 int x,y,z;64 for(int i=1;i<=n;i++) point[i].num=i;65 while(m--)66 {67 scanf ("%d%d%d",&x,&y,&z);68 add(x,y,z);69 add(y,x,z);70 }71 dijkstra(a);72 printf("%d",point[b].dis);73 return 0;74 }
That's all,thanks for watching.