struct ShortestPath
{
typedef int type;
static const int inf=1e9;
static const int __=100005;
struct edge
{
int nex;type dis;
edge() {}
edge(int x,type y):
nex(x),dis(y) {}
bool operator<(const edge& b)const
{
return dis>b.dis;
}
};
int n;
type dis[__];
bool vis[__];
vector<edge>G[__];
priority_queue<edge>Q;
type& operator[](int x){return dis[x];}
void init(int _n)
{
n=_n;
for(int i=1;i<=n;++i)
{
vis[i]=false;
dis[i]=inf;
}
}
void add_edge(int x,int y,type dis)
{
G[x].push_back(edge(y,dis));
}
//先调用init
void Dijkstra(int st)
{
dis[st]=0,Q.push(edge(st,0));
while(!Q.empty())
{
int t=Q.top().nex;Q.pop();
if(vis[t])continue;
vis[t]=true;
for(edge &x:G[t])
if(!vis[x.nex] && dis[t]+x.dis<dis[x.nex])
{
dis[x.nex]=dis[t]+x.dis;
Q.push(edge(x.nex,dis[x.nex]));
}
}
}
void clear()
{
for(int i=1;i<=n;++i)
G[i].clear();
}
}D;
Shortest Path
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- [编程题]比较重量小明陪小红去看钻石，他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们...
