for(x=0;ch>='0'&&ch<='9';ch=CH)x=x*10+ch-48;
}
inline void add(int x,int y,int z)
{
w++;pre[w]=last[x];last[x]=w;other[w]=y;ju[w]=z;
}
void dijkstra(int x)
{
pp po;int p,point,w1;
memset(dist,42,sizeof(dist));dist[x]=0;
memset(flag,0,sizeof(flag));
priority_queue<pp,vector<pp>,greater<pp> >heap;heap.push(make_pair(0,x));
while(heap.size())
{
po=heap.top();p=po.second;heap.pop();
if(flag[p])continue;flag[p]=1;
for(w1=last[p];w1;w1=pre[w1])
if(dist[p]+ju[w1]<dist[point=other[w1]])
{
dist[point]=dist[p]+ju[w1];
heap.push(make_pair(dist[point],point));
}
}
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
scanf("%d%d%d%d%d",&m,&n,&home,&noi,&cmo);
for(i=1;i<=m;i++)read(x),read(y),read(z),add(x,y,z),add(y,x,z);
dijkstra(noi);ans=dist[home]+dist[cmo];
dijkstra(cmo);ans=min(ans,dist[home]+dist[noi]);
printf("%d\n",ans);
return 0;
}
K 短路
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
#define maxn 1100