求助,关于vector
查看原帖
求助,关于vector
21610
雄鹰展翅楼主2020/5/5 00:05

这份代码中的

for(i=0;i<x.size();i++)

如果换成

for(i=0;i<=x.size()-1;i++)

就无法通过,请问是为什么

#include<iostream>
#include<vector>
#include<string.h>
#include<queue>
#define ll long long
#define pa pair<ll,int>
#define N 300005
#define M 300005
using namespace std;

int n,m,S,m0=1;
int h[N],pre[N];
ll dis[N],ans;
bool vis[N],a[2*M];
struct edge{
    int next,to,w;
}e[2*M];
priority_queue<pa,vector<pa>,greater<pa> >q;
vector<int> x;

void ins(int u,int v,int w){
    e[++m0]=(edge){h[u],v,w};h[u]=m0;
}

void dijkstra(int s){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0,q.push(make_pair(0,s));
	
	while(!q.empty()){
		int u=q.top().second; q.pop();
		if(vis[u]) continue; vis[u]=1;
		for(int i=h[u];i;i=e[i].next){
			int v=e[i].to;
			if(!vis[v]&&dis[v]>=dis[u]+e[i].w){
				if(dis[v]>dis[u]+e[i].w) pre[v]=i;
				else if(e[i].w<e[pre[v]].w) pre[v]=i;
				dis[v]=dis[u]+e[i].w;
				q.push(make_pair(dis[v],v)); 
			}
		}
	} 
	
}

int main(){
	int i,u,v,w;
    cin>>n>>m;
	for(i=1;i<=m;i++) cin>>u>>v>>w,ins(u,v,w),ins(v,u,w); 
	cin>>S;
	
    dijkstra(S);
    for(i=1;i<=n;i++) a[pre[i]]=1;
    for(i=2;i<=m0;i+=2)
        if(a[i]||a[i+1]) x.push_back(i/2),ans+=e[i].w;
    
    cout<<ans<<endl;
    for(i=0;i<x.size();i++) cout<<x[i]<<' ';
    return 0;
}
2020/5/5 00:05
加载中...