使用优先队列优化过的dijkstra时间复杂度可以达到O（v*logn），还是很快的。
#include <iostream> //最好是用long long 类型的。
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int maxe=2e5+7;
const int maxv=1e5+7;
int n,m,k,con=0;
ll dis[maxv*12+7];
ll head[maxv*12+7];
int vis[maxv*12+7];
struct node//以边为重点。
{
int u,v,value,next;
node (int u=0,int v=0,int value=0,int next=0):u(u),v(v),value(value),next(next){}
}e[2*maxe*12+7];
struct Node
{
int id;
ll value;
Node(int id,ll value):id(id),value(value){} //结构体是和普通的数据差不多。直接写上就能用吧。
bool operator < (const Node &a)const //优先队列按照从小到大的顺序输出。
{
return value>a.value ;
}
};
void addedge(int u,int v,int value) //唯有结构体数组才可以进行模拟链表。
{
e[con]=node(u,v,value,head[u]);
head[u]=con++;
}
void dig()
{
priority_queue< Node >q;
q.push( Node(1,0));
dis[1]=0;
vis[1]=1;
Node temp(0,0) ; //之后进行验证结构体和类之间的关系。
while(!q.empty())
{
temp=q.top();
q.pop();
int u=temp.id ;
vis[u]=1;
for(int i=head[u];~i;i=e[i].next ) //但是到下一个点的距离确是可以进行优化的。
{
ll v=e[i].v ;
if( vis[ v ]==1 )continue;
if( temp.value + e[i].value <dis[ v ] )//此时的距离吗。
{
dis[ v ]= temp.value +e[i].value ; //最为重要的入队没有考虑啊。
q.push( Node( v,dis[v] ) );
}
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
con=0; //一定不要忘了进行初始化的啊。这里是很重要的。
memset(head,-1,sizeof(head));
memset(dis,125,sizeof(dis));
memset(vis,0,sizeof(vis));
scanf("%d %d %d",&n,&m,&k);
int u,v,value;
for(int i=0;i<m;i++) //因为要建立分层图，所以存储图的数组的长度应该是（2*maxe*（k+2））;
{
scanf("%d %d %d",&u,&v,&value);
for(int j=0;j<=k;j++)
{
addedge( u+n*j,v+n*j,value );
if(j!=k)
addedge(u+n*j,v+n*(j+1),0); //建立层与层之间的关联。
}
}
dig();
ll ans=9042521604759584125;
for(int i=0;i<=k;i++)
if(dis[n+n*i]<ans)
ans=dis[n+n*i];
printf("%lld\n",ans);
}
return 0;
}
