#include <iostream> #include<stdio.h> #include<stdlib.h> #include<vector> #include<cstring> using namespace std; int mp[510][510]; int d[510]; int res[510]; int st; int ed; vector<int> pre[510]; int m; int n; bool f[510]; int cnt=0; void input() { scanf("%d %d %d %d",&n,&m,&st,&ed); for(int i=0;i<n;i++) { scanf("%d",&res[i]); // pre[i].push_back(i); // d[i]=0x3f3f3f3f; } pre[st].push_back(st); int a,b,c; for(int i=0;i<m;i++) { scanf("%d %d %d",&a,&b,&c); mp[a][b]=mp[b][a]=c; } } void dijkstra() { memset(d,0x3f,sizeof(d)); memset(f,true,sizeof(f)); int N=n; d[st]=0; while(N--) { int min=0x3f3f3f3f; int u=0; for(int i=0;i<n;i++) { if(f[i]==true&&d[i]<min) { min=d[i]; u=i; } } if(min==0x3f3f3f3f) break; f[u]=false; for(int v=1;v<n;v++) { if(mp[u][v]!=0) { //if(f[v]&&d[v]>d[u]+mp[u][v]) if(d[v]>=d[u]+mp[u][v]) { d[v]=d[u]+mp[u][v]; pre[v].push_back(u); } } } } // for(int i=0;i<n;i++) cout<<d[i]<<" "; // cout<<endl; // cout<<"pre: "<<endl; // for(int i=0;i<n;i++) // { // for(int j=0;j<pre[i].size();j++) // { // cout<<pre[i][j]<<" "; // } // cout<<endl; // } } int ans=0; int mx=0; void get(int n) { if(n==ed) { mx+=res[n]; } if(pre[n][0]==n) { // mx+=res[n]; cnt++; if(mx>ans) { ans=mx; } return; } else { for(int i=0;i<pre[n].size();i++) { mx+=res[pre[n][i]]; get(pre[n][i]); mx-=res[pre[n][i]]; } } } int main() { //freopen("input.txt","r",stdin); input(); dijkstra(); get(ed); printf("%d %d\n",cnt,ans); return 0; }
提交了两次一直CE,error:reference to 'prev' is ambiguous
原因是prev重名了。