#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
struct po
{
	int shu,dist,qian;
	bool operator < (const po&other) const{
		return dist>other.dist;
	}
};
struct pp
{
	int shu,quan,qian;
};
int meiyong[1];
vector<pp>ve[10005];
priority_queue<po>Q;
bool vist[20005];
int dis[20005];
int qian[20005];
int main()
{
	//freopen("heap.in","r",stdin);
	//freopen("heap.out","w",stdout);
	int n,e,i,j,t;
	pp go;
	memset(meiyong,127,sizeof(meiyong));
	cin>>t>>n>>e;
	for(i=1;i<=e;i++)
    {
		int x,y,q,l;
		cin>>x>>y>>q>>l;
		go.shu=y;
		go.quan=q;
		go.qian=l;
		ve[x].push_back(go);
	}
	/*for(i=1;i<=n;i++)
	{
		for(j=0;j<ve[i].size();j++)
			cout<<ve[i][j].shu<<" ";
		cout<<endl;
	}
	for(i=1;i<=n;i++)
	{
		for(j=0;j<ve[i].size();j++)
			cout<<ve[i][j].qian<<" ";
		cout<<endl;
	}*/
	po ls;
	ls.shu=1;
	ls.dist=0;
	ls.qian=t;
	Q.push(ls);
	//cout<<meiyong[0]<<endl;
	/*for(i=2;i<=n;i++)
	{
		ls.shu=i;
		ls.dist=meiyong[0];
		Q.push(ls);
	}*/
	i=0;
	while(i!=2*n)
	{
		if(Q.empty())
		    break;
		//if(i==5)
		//    int jieyong=0;
		int dds=Q.top().shu,ddd=Q.top().dist,ddq=Q.top().qian;
		if(ddq<0)
		{
			Q.pop();
			continue;
		}
		//cout<<dds<<" "<<ddd<<" "<<ddq<<endl;
		for(j=0;j<ve[dds].size();j++)
		{
			if(!vist[ve[dds][j].shu])
			{
				ls.shu=ve[dds][j].shu;
				ls.dist=ddd+ve[dds][j].quan;
				ls.qian=ddq-ve[dds][j].qian;
				Q.push(ls);
			}
		}
		int tt;
		//cout<<"*****"<<Q.top().shu<<"*****"<<endl;
		tt=Q.top().qian;
		if(tt<0)
		{
			Q.pop();
			continue;
		}
		//t=tt;
		i++;
		if(!vist[Q.top().shu])
		{
			vist[Q.top().shu]=1;
			dis[Q.top().shu]=Q.top().dist;
		}
		if(vist[n])
		    break;
		Q.pop();
	}
	if(vist[n])
	    cout<<dis[n];
	else cout<<"-1";
	return 0;
}

• Re:有重邊，vector怎麼辦。。。附wrong answer代碼--》 (2106) 20090527 2020-12-13 22:22:07
• Re:有重邊，vector怎麼辦。。。附wrong answer代碼--》 (2106) 20090527 2020-12-13 22:22:08