@[BigYellowDog](/space/show?uid=91681) 迪杰特斯拉+Heap了解一下
by dingxingdi @ 2018-04-18 23:36:17
Dij**k**stra，以及不加堆优化是过不了的= =
by panda_2134 @ 2018-04-19 07:32:35
@[BigYellowDog](/space/show?uid=91681) 讲道理普通dij应该有70啊。。dij重边不需要挂前向星的，开个邻接矩阵就行了。因为根据贪心2个点之间肯定是要选更短的那条边。
by sxyugao @ 2018-04-19 08:46:38
蒟蒻的板子了解一下
```cpp
#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
struct edge
{
int to,cost;
};
struct node
{
int len,v;
friend bool operator <(node x,node y)
{
return x.len>y.len;
}
};
int dis[10100];
int n,m,s;
vector<edge>G[500050];
void Dijkstra()
{
fill(dis,dis+10050,2147483647);
priority_queue<node>q;
dis[s]=0;
node t;
t.len=0;
t.v=s;
q.push(t);
while(q.size())
{
t=q.top();
q.pop();
if(dis[t.v]<t.len) continue;
for(int i=0;i<G[t.v].size();i++)
{
edge e=G[t.v][i];
if(dis[e.to]>dis[t.v]+e.cost)
{
dis[e.to]=dis[t.v]+e.cost;
node temp={dis[e.to],e.to};
q.push(temp);
}
}
}
}
inline int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
return x;
}
int main()
{
int t;
scanf("%d %d %d",&n,&m,&s);
for(int i=0;i<m;i++)
{
int a,b,w;
edge t,rt;
a=read();
b=read();
w=read();
t.to=b;
t.cost=w;
G[a].push_back(t);
}
Dijkstra();
for (int i=1;i<=n;i++)
printf("%d ",dis[i]);
return 0;
}
```
by AcerMo @ 2018-04-20 15:48:45
@[BigYellowDog](/space/show?uid=91681)
by AcerMo @ 2018-04-20 15:49:01
@[_Acer_](/space/show?uid=71558)
好的谢谢！现已AC
by Error_666 @ 2018-04-20 20:01:23
%%%%%@[BigYellowDog](/space/show?uid=91681)
by AcerMo @ 2018-04-20 22:00:10
@[_Acer_](/space/show?uid=71558)
敢问%%%%%是什么意思:D
by Error_666 @ 2018-04-21 00:16:37