zoj1655(最短路)

2017年07月27日 11点热度 0人点赞 0条评论

zoj1655(最短路)

//求n到其他点的损率的乘积最大 
#include
#include
#include
#include
using namespace std;
const int mn=105,mm=40005;
struct Edge{
	int to,next;
	double w;
}edges[mm];
int n,m,head[mn],tot,inq[mn];
double dis[mn],w[mn];
void add(int u,int v,double w)
{
	edges[tot].to=v;
	edges[tot].w=w;
	edges[tot].next=head[u];
	head[u]=tot++;
	
	edges[tot].to=u;
	edges[tot].w=w;
	edges[tot].next=head[v];
	head[v]=tot++;
}
void spfa()  
{
	memset(dis,0,sizeof(dis));//这个地方要注意啊 
    memset(inq,0,sizeof(inq));  
    dis[n]=1;  
    inq[n]=1;  
    deque q;  
    q.push_back(n);  
    while(q.size())  
    {  
        int x=q.front();  
        q.pop_front();  
        inq[x]=0;  
        for(int i=head[x];~i;i=edges[i].next)  
        {  
            int v=edges[i].to;  
            if(dis[v]dis[q.front()])  
                    q.push_front(v);  
                    else q.push_back(v);  
                    inq[v]=1;  
                }  
            }  
        }  
    }  
}
int main(){
	int u,v;
	double ww;
	while(~scanf("%d%d",&n,&m))
	{
		tot=0;
		memset(head,-1,sizeof(head));
		for(int i=1;i
未经允许不得转载!zoj1655(最短路)

update

纸上得来终觉浅, 绝知此事须躬行。