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
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。
推荐阅读更多精彩内容
- [编程题]比较重量小明陪小红去看钻石,他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们...